Leetcode 94. 二叉树的中序遍历
算法
发布于: 2021-09-17

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

示例 1:

91-1.jpg

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

示例 2:

输入:root = []
输出:[]

示例 3:

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

示例 4:

94-2.jpg

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

示例 5:

94-3.jpg

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

提示:

  • 树中节点数目在范围 [0, 100]

  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解

递归算法命名很简单,我就不使用迭代算法~ 洒洒水啦~

不知道大家有没有感想,前序/中序/后序 记了好多遍根本记不住顺序好嘛,不说了,还有一个 BOSS 平衡二叉树使用中序还是前序,这个一定要记好😭

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    } else {
        res = append(res, inorderTraversal(root.Left)...)
        res = append(res, root.Val)
        res = append(res, inorderTraversal(root.Right)...)
    }

    return res

}