递归模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 前序位置
    traverse(root.Left)
    // 中序位置
    traverse(root.Right)
    // 后序位置
}

层序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
func levelTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := make([]*TreeNode, 0)
    q = append(q, root)

    // 从上到下遍历二叉树的每一层
    for len(q) > 0 {
        sz := len(q)
        // 从左到右遍历每一层的每个节点
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            // 将下一层节点放入队列
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
    }
}

遇到一道二叉树的题目时的通用思考过程是：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。

3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。

一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历.

参考链接： https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/dong-ge-da-334dd/