关于golang:Golang力扣Leetcode中级算法树和图二叉树的中序遍历递归迭代

题目：给定一个二叉树的根节点 root，返回它的 中序 遍历。

链接：力扣 Leetcode—中级算法—树和图—二叉树的中序遍历.

示例 1 ：

输出：root = [1,null,2,3]
输入：[1,3,2]

示例 2 ：

输出：root = []
输入：[]

示例 3 ：

输出：root = [1]
输入：[1]

示例 4 ：

输出：root = [1,2]
输入：[2,1]

示例 5 ：

输出：root = [1,null,2]
输入：[1,2]

标签：栈、树、深度优先搜寻、二叉树

思路 ：二叉树的中序遍历，依照拜访左子树——根节点——右子树的形式遍历这棵树，而在拜访左子树或者右子树的时候咱们依照同样的形式遍历，直到遍历完整棵树。因而整个遍历咱们能够间接用 递归 函数来模仿这一过程。或者咱们也能够用 迭代 来解决问题，先将整颗树怼进去，在把所有的左子树怼进去，而后遍历左子树，间接右边的最下边。因为先进后出，拿到了最上面的左节点，也怼到数组里，看以右节点为根的还有没有左节点，有就回到下面第 1 步，没有就走第 3 步，把根节点怼进去，在怼右节点。

递归 Go 代码如下：

package main

import "fmt"

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int       // 根
    Left  *TreeNode // 左节点
    Right *TreeNode // 右节点
}

func inorderTraversal(root *TreeNode) (res []int) {var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {return // 完结以后递归}
        inorder(node.Left)          // 间接怼到右边最下边
        res = append(res, node.Val) // 增加到数组里
        inorder(node.Right)         // 看左边还有没有分支，有就持续走，没有就将右节点退出数组
    }
    inorder(root)
    return
}

func main() {// 测试用例 root = [1,null,2,3]
    root := &TreeNode{1, nil, nil}
    root.Right = &TreeNode{2, nil, nil}
    root.Right.Left = &TreeNode{3, nil, nil}

    res := inorderTraversal(root)
    fmt.Printf("res is: %v\n", res)
}

提交截图 ：

迭代 Go 代码如下：

package main

import "fmt"

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int       // 根
    Left  *TreeNode // 左节点
    Right *TreeNode // 右节点
}

func inorderTraversal(root *TreeNode) (res []int) {
    // 定义一个栈，栈存的就是一棵树
    var stack []*TreeNode
    for root != nil || len(stack) > 0 {
        for root != nil {
            // 1. 先将整颗树怼进去，在把所有的左子树怼进去
            stack = append(stack, root)
            // 2. 遍历左子树，间接右边的最下边
            root = root.Left
        }
        // 3. 因为先进后出，拿到了最上面的左节点
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 4. 怼到数组里
        res = append(res, root.Val)
        //5. 看以右节点为根的还有没有左节点，有就回到下面第 1 步，没有就走第 3 步，把根节点
        root = root.Right
    }
    return
}

func main() {// 测试用例 root = [1,null,2,3]
    root := &TreeNode{1, nil, nil}
    root.Right = &TreeNode{2, nil, nil}
    root.Right.Left = &TreeNode{3, nil, nil}

    res := inorderTraversal(root)
    fmt.Printf("res is: %v\n", res)
}

提交截图：