Levon's Blog

微信: L6241425

0%

算法-树

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 9.1k 阅读时长 ≈ 8 分钟

两个套路，一个是递归遍历二叉树traverse() 无返回值 ，一个是分解处理子数，有返回值。

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

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

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

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

1. 常考

1.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
26
27
28
29

var res int // 记录最大深度
var depth int // 记录遍历到的节点的深度


func maxDepth(root *TreeNode) int {
	traverse(root)
	return res
}

func traverse(root *TreeNode) {
	if root == nil {
		return
	}
	depth++
	if root.Left == nil && root.Right == nil {
		res = max(res, depth) 		// 到达叶子节点，更新最大深度
	}
	traverse(root.Left)
	traverse(root.Right)
	depth--
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
  • 分解问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    return Max(left,right)+1
}
// 但为什么主要的代码逻辑集中在后序位置？
// 通过子树的最大深度推导出原树的深度，所以当然要首先利用递归函数的定义算出左右子树的最大深度，然后推出原树的最大深度，主要逻辑自然放在后序位置。

func Max(a, b int) int{
    if a > b {
        return a
    }
    return b
}

1.2 判断平衡二叉树 🔥

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
func isBalanced(root *TreeNode) bool {
    if root == nil{
        return true
    }
    if !isBalanced(root.Left) || !isBalanced(root.Right){
        return false
    }
    if abs(maxDepth(root.Left)-maxDepth(root.Right)) > 1 {
        return false
    }
    return true
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left),maxDepth(root.Right)) + 1
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a 
}

1.3 翻转二叉树🔥

1
2
3
4
5
6
7
8
9
10
11
func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil{
        return nil
    }

    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)
    root.Left = right
    root.Right = left
    return root
}

2. 其他

2.1 二叉树的直径

每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。

+ 重建二叉树(中等)

  • 画图, len(preorder[:pos]) 是左子树的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0{
        return nil 
    }

    root := &TreeNode{preorder[0],nil,nil}
    pos := 0
    for ; pos < len(inorder); pos++{
        if inorder[pos] == preorder[0]{
            break
        }
    }

    root.Left = buildTree(preorder[1:len(preorder[:pos])+1],inorder[:pos]) 
    root.Right =  buildTree(preorder[len(preorder[:pos])+1:],inorder[pos+1:]) 
    return root
}

+ 合并二叉树(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil{
        return root2
    }
    if root2 == nil{
        return root1
    }

    root1.Val = root1.Val + root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1  
}

+ 相同的树(简单)

1
2
3
4
5
6
7
8
9
10
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }

    return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

+ 另一个树的子树(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil || subRoot == nil {
        return false
    }

    if isSameTree(root, subRoot) {
        return true
    }

    return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}


func isSameTree(p *TreeNode, q *TreeNode) bool {
  if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }

    return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

+ 树的子结构(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }

    return isContain(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
    
}


// A,B根节点相同，B是不是A的子结构
func isContain(A *TreeNode, B *TreeNode) bool {
    if B == nil {
        return true
    }
    if A == nil {
        return false
    }
    if A.Val != B.Val {
        return false
    }
    return isContain(A.Left, B.Left) && isContain(A.Right, B.Right)
}

+ 单值二叉树(简单)

1
2
3
4
5
6
7
8
9
10
11
12
func isUnivalTree(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if root.Left != nil && root.Val != root.Left.Val {
        return false
    }
    if root.Right != nil && root.Val != root.Right.Val {
        return false
    }
    return isUnivalTree(root.Left) && isUnivalTree(root.Right)
}

+ 对称的二叉树(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}


func isMirror(l, r *TreeNode) bool {
    if l == nil && r == nil {
        return true
    }
    if l == nil || r == nil{
        return false
    }

   return l.Val == r.Val && isMirror(l.Right, r.Left) && isMirror(l.Left,r.Right)
}

+ 二叉搜索树的最近公共祖先(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	val := root.Val
    pv := p.Val
    qv := q.Val

    if pv > val && qv > val {
        return lowestCommonAncestor(root.Right, p, q)
    }else if pv < val && qv < val {
        return lowestCommonAncestor(root.Left, p, q)
    }else{
        return root
    }
}

+ 二叉树的最近公共祖先 (中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if p == root || q == root {
        return root
    }

    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right,p, q)
    if l != nil && r != nil {// 左右各一个
        return root
    }
    if l != nil {// 两都在左边
        return l
    }
    if r != nil{ // 两都在右边
        return r
    }

    return nil
}

+ 二叉搜索树的第k大节点(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var arr[]int

func kthLargest(root *TreeNode, k int) int {
    if root == nil {
        return 0
    }
    arr = []int{}
    dfs(root)
    return arr[k-1]
}

func dfs(root *TreeNode) {
    if root == nil  {
        return 
    }
    dfs(root.Right)
    arr = append(arr, root.Val)
    dfs(root.Left)
}

+ 二叉树中和为某一值的路径(中等) TODO

+ 二叉搜索树的后序遍历序列(中等) TODO

+ 二叉搜索树与双向链表(中等) TODO

3. 算法理解

3.1 两种思路解题

二叉树的前序遍历结果怎么算？

  • 回朔算法核心思路（递归遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
List<Integer> res = new LinkedList<>();
List<Integer> preorder(TreeNode root) {
    traverse(root);
		return res; 
}

void traverse(TreeNode root) { // 没有返回值
    if (root == null) {
			return; 
    }
    res.addLast(root.val);
    traverse(root.left);
    traverse(root.right);
}
  • 动态规划核心思路 （分解）
1
2
3
4
5
6
7
8
9
10
11
12
List<Integer> preorder(TreeNode root) {
   List<Integer> res = new LinkedList<>();
   if (root == null) {
			return res; 
   }

	res.add(root.val);
  res.addAll(preorder(root.left)); 
 	res.addAll(preorder(root.right));
  return res
}

3.2 深入理解前中后序

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的List

前序位置的代码在刚刚进入一个二叉树节点的时候执行；

后序位置的代码在将要离开一个二叉树节点的时候执行；

中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

3.3 后序加强

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

只有后序位置才能通过返回值获取子树的信息。换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。

3.4 DFS 又是什么

动态规划/DFS/回溯算法 都可以看做二叉树问题的扩展，只是它们的关注点不同：

  • 动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。
  • 回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
  • DFS 算法属于遍历的思路，它的关注点在单个「节点」。
动态规划
1
2
3
4
5
6
7
8
9
10
11
// 计算这棵二叉树共有多少个节点。
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 我这个节点关心的是我的两个子树的节点总数分别是多少
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置，左右子树节点数加上自己就是整棵树的节点数
    return leftCount + rightCount + 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
// 用遍历的思路写一个 traverse 函数，打印出遍历这棵二叉树的过程
void traverse(TreeNode root) {
    if (root == null) return;
    printf("从节点 %s 进入节点 %s", root, root.left);
    traverse(root.left);
    printf("从节点 %s 回到节点 %s", root.left, root);

    printf("从节点 %s 进入节点 %s", root, root.right);
    traverse(root.right);
    printf("从节点 %s 回到节点 %s", root.right, root);
}


void backtrack(...) {
    for (int i = 0; i < ...; i++) {
        // 做选择
        ...

        // 进入下一层决策树
        backtrack(...);

        // 撤销刚才做的选择
        ...
    }
}

这就是回溯算法遍历的思路，它的着眼点永远是在节点之间移动的过程，类比到二叉树上就是「树枝」。

DFS (深度优先搜索)
1
2
3
4
5
6
7
8
9
// 写一个 traverse 函数，把这棵二叉树上的每个节点的值都加一。

void traverse(TreeNode root) {
    if (root == null) return;
    // 遍历过的每个节点的值加一
    root.val++;
    traverse(root.left);
    traverse(root.right);
}

这就是 DFS 算法遍历的思路，它的着眼点永远是在单一的节点上，类比到二叉树上就是处理每个「节点」。

3.5 DFS 和回朔区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// DFS 算法把「做选择」「撤销选择」的逻辑放在 for 循环外面
void dfs(Node root) {
    if (root == null) return;
    // 做选择
    print("我已经进入节点 %s 啦", root)
    for (Node child : root.children) {
        dfs(child);
    }
    // 撤销选择
    print("我将要离开节点 %s 啦", root)
}

// 回溯算法把「做选择」「撤销选择」的逻辑放在 for 循环里面
void backtrack(Node root) {
    if (root == null) return;
    for (Node child : root.children) {
        // 做选择
        print("我站在节点 %s 到节点 %s 的树枝上", root, child)
        backtrack(child);
        // 撤销选择
        print("我将要离开节点 %s 到节点 %s 的树枝上", child, root)
    }
}

看到了吧，你回溯算法必须把「做选择」和「撤销选择」的逻辑放在 for 循环里面，否则怎么拿到「树枝」的两个端点？

3.6 层序遍历 (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);

    // 从上到下遍历二叉树的每一层
    while (!q.empty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 将下一层节点放入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
    }
}

4. 参考资料

可以加首页作者微信，咨询相关问题！