94. 二叉树的中序遍历

题目#

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

示例 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]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

思路#

中序遍历，即以左-根-右的顺序遍历二叉树。

递归#

递归比较简单，左中右即可。

迭代#

迭代的思路即是手动维护遍历栈即可。

代码#

递归#

func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    inorder(root, &result)
    return result
}

func inorder(root *TreeNode, res *[]int) {
    if root != nil {
        inorder(root.Left, res)
        *res = append(*res, root.Val)
        inorder(root.Right, res)
    }
}

迭代#

func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    // 栈
    stack := []*TreeNode{}

    // 跳出遍历的条件
    for root != nil || len(stack) != 0 {
        // 最开始，会走一遍这个循环
        // 走完后，root 处在整棵树最左下
        for root != nil {
            // 加入栈中
            stack = append(stack, root)
            // 向左走
            root = root.Left
        }

        // 出栈
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        result = append(result, root.Val)

        // 这时往右走
        // 之后又会走上面那个循环
        root = root.Right
    }

    return result
}