如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。

DFS 深度搜索和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

二叉树的递归遍历

递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

Leetcode: 144. 二叉树的前序遍历

C++版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
void traversal(TreeNode *cur, vector<int> &res) //1、递归需要的参数和返回值
{
    if(NULL == cur) //2、递归终止条件，当前节点等于空，直接返回
    {
        return;
    }
    //3、递归中的逻辑，前序遍历（中左右）
    res.push_back(cur->val);
    traversal(cur->left, res);
    traversal(cur->right, res);
}

go版本：

1
2
3
4
5
6
7
8
func traversal(root *TreeNode, res *[]int) {
    if root == nil{
        return
    }
    *res = append(*res, root.Val)
    traversal(root.Left, res)
    traversal(root.Right, res)
}

分治法

先分别处理局部，再合并结果

适用场景

  • 快速排序
  • 归并排序
  • 二叉树相关问题

分治法模板

  • 递归返回条件
  • 分段处理
  • 合并结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func preorderTraversal(root *TreeNode) []int {
    return divideAndConquer(root)
}

func divideAndConquer(root *TreeNode) []int {
    res := make([]int, 0)
    // 返回条件(null & leaf)
    if root == nil {
        return res
    }

    // 分治
    left := divideAndConquer(root.Left)
    right := divideAndConquer(root.Right)

    // 合并结果
    res = append(res, root.Val)
    res = append(res, left...)
    res = append(res, right...)
    return res
}

二叉树的层序遍历

层序遍历一个二叉树,就是从左到右一层一层的去遍历二叉树。就是图论中的广度优先搜索在二叉树中的应用，需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

层序遍历每个值

Leetcode：107.二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

给定二叉树 [3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

返回其自底向上的层序遍历为：

[

[15,7],

[9,20],

[3]

]

C++版本：

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
26
27
28
vector<vector<int>> levelOrderBottom(TreeNode* root) 
{
    //层序遍历方式就是图论中的广度优先遍历
    //用辅助队列实现，先进先出，符合一层一层遍历的逻辑
    queue<TreeNode*> que;
    if(NULL != root)
    {
        que.push(root);
    }
    vector<vector<int> > res;
    while(!que.empty())   //循环一次，处理树的一层
    {
        //开始对处理队列里的值，先取出当前队列中节点的val，然后队列弹出该值，然后再获取节点的左右节点，存入队列中
        int iSize = que.size();   //循环一次，处理一个节点
        vector<int> vec;
        for(int i = 0; i < iSize; ++i)// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
        {
            TreeNode *cur = que.front();
            vec.push_back(cur->val);
            que.pop();  //弹出在front位置的值
            if(cur->left != NULL)   que.push(cur->left);
            if(cur->right != NULL)   que.push(cur->right);
        }
        res.push_back(vec);
    }
    reverse(res.begin(), res.end());    //最后进行翻转
    return res;
}

go版本：

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
26
27
28
29
30
31
32
func levelOrderBottom(root *TreeNode) [][]int {
    res := make([][]int, 0, 10)

    queue := make([]*TreeNode, 0, 10)
    if root == nil{
        return res
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)

        level := make([]int, 0, 10)
        for i:=0; i < size; i++ {
            cur := queue[0]    //  永远都是取第0个
            queue = queue[1:]  // 截断，取后面值
            level = append(level, cur.Val)	// 收集当前层的值
            // 收集下一层的节点
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        res = append(res, level)
    }

    for i := 0; i < len(res) / 2; i++ {
        res[i], res[len(res) - 1 - i] = res[len(res) - 1 - i], res[i]
    }
    return res
}

二叉树的右视图

Leetcode：199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

如：

​ 3

/ \

9 20

​ / \

​ 15 7

以上二叉树的右视图是 3,20,7

思路：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

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
26
27
28
29
30
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)

    res := make([]int, 0)

    for len(queue) > 0 {
        size := len(queue)

        for i := 0; i < size; i++{
            cur := queue[0]
            queue = queue[1:]
            if i == (size - 1) {	// 收集每一层最后的节点值
                res = append(res, cur.Val)
            }
            if cur.Left != nil{
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil{
                queue = append(queue, cur.Right)
            }
        }
    }

    return res
}

二叉树的层平均值

Leetcode：199.二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

思路：本题就是层序遍历的时候把一层求个总和在取一个均值。

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
26
27
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)

    res := make([]int, 0)

    for len(queue) > 0 {
        size := len(queue)
        sum := 0
        for i := 0; i < size; i++{
            cur := queue[0]
            queue = queue[1:]
            sum += cur.Val
            if cur.Left != nil{
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil{
                queue = append(queue, cur.Right)
            }
        }
        res = append(res, sum/size)
    }
}

N 叉树的层序遍历

Leetcode：429.N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

思路：这道题依旧是模板题，只不过一个节点有多个孩子了

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
26
27
28
func levelOrder(root *Node) []int {
    if root == nil {
        return nil
    }

    queue := make([]*Node, 0)
    queue = append(queue, root)

    res := make([][]int, 0)

    for len(queue) > 0 {
        size := len(queue)

        level := make([]int, 0, 10)
        for i:=0; i < size; i++ {
            cur := queue[0]    //  永远都是取第0个
            queue = queue[1:]  // 截断，取后面值
            level = append(level, cur.Val)	// 收集当前层的值
            // 收集下一层的节点
            for j := 0; j < len(cur.Children); j++ {
                queue = append(queue, cur.Children[j])
            }
        }
        res = append(res, level)
    }

    return res
}

在每个树行中找最大值

Leetcode：515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

思路：层序遍历中，在处理每一层时，实时判断当前处理的值是否是最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for len(queue) > 0 {
    size := len(queue)
    maxNode := math.MinInt64
    
    for i:=0; i < size; i++ {
        cur := queue[0]    // 永远都是取第0个
        queue = queue[1:]  // 截断，取后面值
        level = append(level, cur.Val)	// 收集当前层的值
        if maxNode < cur.Val{
            maxNode = cur.Val
        }
        // 收集下一层的节点
        if cur.Left != nil{
            queue = append(queue, cur.Left)
        }
        if cur.Right != nil{
            queue = append(queue, cur.Right)
        }
    }
    res = append(res, maxNode)
}

二叉树的最大深度

Leetcode：104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

思路：

层序遍历

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
26
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    
    maxDepth := 0
    for len(queue) > 0 {
        maxDepth++

        size := len(queue)

        for i := 0; i < size; i++{
            cur := queue[0]
            queue = queue[1:]
            if cur.Left != nil{
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil{
                queue = append(queue, cur.Right)
            }
        }
    }
    return maxDepth
}

分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxDepth(root *TreeNode) int {
    // 返回条件
    if root == nil {
        return 0
    }

    // 分治思想
    leftCount := maxDepth(root.Left)
    rightCount := maxDepth(root.Right)

    if leftCount > rightCount {
        return leftCount + 1    // 当前节点的深度等于其子树的最大深度加上自身的深度（即1）
    }
    return rightCount + 1
}

二叉树的最小深度

Leetcode：111. 二叉树的最小深度

给定一个二叉树 root ，返回其最小深度。

思路：当左右节点都为空的时候，就说明当前节点是最底层了

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
26
27
28
29
30
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    
    minDepth := 0
    for len(queue) > 0 {
        minDepth++

        size := len(queue)

        for i := 0; i < size; i++{
            cur := queue[0]
            queue = queue[1:]
            // 当左右节点都为空的时候，就说明当前节点是最底层了
            if cur.Left == nil && cur.Right == nil {
                return minDepth
            }
            if cur.Left != nil{
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil{
                queue = append(queue, cur.Right)
            }
        }
    }
    return minDepth
}

平衡二叉树

Leetcode：110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：分治法，平衡是指左边平衡 && 右边平衡 && 左右两边高度 <= 1， 需要返回高度及是否平衡。

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 isBalanced(root *TreeNode) bool {
    _, isBalance := maxDepth(root)
    return isBalance
}

func maxDepth(root *TreeNode) (int, bool){
    // 返回条件
    if root == nil {
        return 0, true
    }

    // 分治
    leftCount, leftIsBalanced := maxDepth(root.Left)
    rightCount, rightIsBalanced := maxDepth(root.Right)

    // 判断是否平衡
    if !leftIsBalanced || !rightIsBalanced || leftCount - rightCount > 1 || rightCount - leftCount > 1{
        return 0, false
    }

    if leftCount > rightCount{
        return leftCount + 1, true  // 左边节点深度加上当前层节点深度（即1）
    }
    return rightCount + 1, true
}

翻转二叉树

Leetcode：226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：递归法使用前序和后序遍历都可以实现，唯独使用中序遍历不可以；同时使用层序遍历也可以实现翻转；主要使用的方法就是交换节点，root.Left, root.Right = root.Right, root.Left

1
2
3
4
5
6
7
8
9
10
11
func invertTree(root *TreeNode) *TreeNode{
    if root == nil {
        return nil
    }
    
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    
    return root
}

对称二叉树

Leetcode：101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

思路：首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func compare(left *TreeNode, right *TreeNode) bool {
    // 判断返回条件有4个
    if left == nil && right != nil {
        return false
    } else if left != nil && right == nil {
        return false
    } else if left == nil && right == nil {
        return true
    } else if left.Val != right.Val {
        return false
    }
    
    // 左右节点不为空，且数值相同的才会往下走
    outside := compare(left.Left, right.Right) // 比较树的外侧是否对称
    inside := compare(left.Right, right.Left) // 比较树的内侧是否对称
    return outside && inside
}

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return compare(root.Left, root.Right)
}

相同的树

Leetcode：100. 相同二叉树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：与对称二叉树类似，先找出递归返回的条件，然后对比两棵树的左节点是否相等，再对比右节点是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isSameTree(p *TreeNode, q *TreeNode) bool {
    // 判断返回条件有4个
    if p != nil && q == nil {
        return false
    } else if p == nil && q != nil {
        return false
    } else if p == nil && q == nil {
        return true
    } else if p.Val != q.Val {
        return false
    }

    // 两个节点不为空，且数值相同的才会往下走
    b1 := isSameTree(p.Left, q.Left)   // 比较两棵树的左节点是否相等
    b2 := isSameTree(p.Right, q.Right)   // 比较两棵树的右节点是否相等

    return b1 && b2
}

另一棵树的子树

Leetcode：572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

思路：先从根节点对比两棵树是否一样，不一样则分别取root树的左节点与右节点跟子树subRoot对比。

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
26
27
28
29
30
31
32
33
34
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    if isSameTree(root, subRoot) {
        return true
    }
    if isSubtree(root.Left, subRoot){   // 两棵树不一样，就传root的左节点继续对比
        return true
    }
    if isSubtree(root.Right, subRoot){   // 两棵树不一样，就传root的右节点继续对比
        return true
    }
    return false
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    // 判断返回条件有4个
    if p != nil && q == nil {
        return false
    } else if p == nil && q != nil {
        return false
    } else if p == nil && q == nil {
        return true
    } else if p.Val != q.Val {
        return false
    }

    // 两个节点不为空，且数值相同的才会往下走
    b1 := isSameTree(p.Left, q.Left)   // 比较两棵树的左节点是否相等
    b2 := isSameTree(p.Right, q.Right)   // 比较两棵树的右节点是否相等

    return b1 && b2
}

二叉树的搜索

Leetcode：700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

​ 4

​ / \

2 7

/ \

1 3

和值: 2

你应该返回如下子树:

2

/ \

1 3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

思路分析：因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

这里可能会疑惑，在递归遍历的时候，什么时候直接return 递归函数的返回值，什么时候不用加这个 return呢。如果要搜索一条边，递归函数就要加返回值，这里也是一样的道理。

因为搜索到目标节点了，就要立即return了，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。

1
2
3
4
5
6
7
8
9
TreeNode* searchBST(TreeNode* root, int val) 
{
    if(root == NULL)    return root;
    if(root->val > val) return searchBST(root->left, val);
    else if(root->val < val)    return searchBST(root->right, val);
    else if(root->val == val)   return root;

    return NULL;
}