94_binary_tree_inorder_traversal

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

代码参考：

package main

import "fmt"

func main() {
    tree := &Tree{}
    tree.root = &TreeNode{Val: 4}
    for _, v := range []int{2, 7, 1, 3, 6, 9} {
        tree.BFSInsert(v)
    }
    tree.BFSTraverse(tree.root)              // 4 2 7 1 3 6 9
    fmt.Println(inorderTraversal(tree.root)) // 1 2 3 4 6 7 9
}

func inorderTraversal(root *TreeNode) []int {
    var res []int
    traverse(root, &res)
    return res
}

// 中序遍历：左子节点 -> 父节点 -> 右子节点
func traverse(node *TreeNode, res *[]int) {
    if node == nil {
        return
    }
    if node.Left != nil {
        traverse(node.Left, res)
    }
    *res = append(*res, node.Val)
    if node.Right != nil {
        traverse(node.Right, res)
    }
}