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)
    }
}
最后编辑: kuteng  文档更新时间: 2021-06-05 10:16   作者:kuteng