Post

算法（二）--二叉树

Posted Updated
By SmallC
19 min read
算法（二）--二叉树

二叉树

二叉树基础及其常见类型

二叉树的重要性将贯穿开发始终。很多实用且复杂的数据结构式基于二叉树的，比如红黑树（二叉搜索树）、多叉树、二叉堆、图、字典、并查集，二叉树是非常重要的基础。如果你想掌握上面的数据类型，掌握二叉树的重要性不言而喻。

同时很多算法思想可以被抽象为二叉树。常见的是回溯算法、动态规划，其过程可以视为二叉树的深度遍历。

  • 满二叉树 中间节点都有左右子节点。深度为h时，节点个数为2^h - 1。
  • 完全二叉树 满二叉树的普遍版，最后一层允许不满。常用于实现二叉堆。
  • 二叉搜索树（BST） 对于每一个中间节点，所有左子节点小于根节点，所有右子节点大于根节点。

二叉树的奇怪实现

  • 数组储存二叉树：二叉堆和并查集
  • 哈希表：unordered_map<int , vector<int>>

二叉树的遍历

  • 递归遍历DFS 根据递归函数的位置不同，可以产生前中后序遍历。
    1
2
3
4
5
6
7
8
9
10
11

    // 二叉树的遍历框架
void traverse(TreeNode* root) {
  if (root == nullptr) {
      return;
  }
  // 前序位置 输出程序位置
  traverse(root->left);
  // 中序位置
  traverse(root->right);
  // 后序位置
}
  • 层序遍历（BFS） 按层遍历，需要使用队列来实现。
    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

    // 常见版本
void levelOrderTraverse(TreeNode* root) {
  if (root == nullptr) {
      return;
  }
  queue<TreeNode*> q;
  q.push(root);
  // 记录当前遍历到的层数（根节点视为第 1 层）
  int depth = 1;

  while (!q.empty()) {
      int sz = q.size();
      for (int i = 0; i < sz; i++) {
          TreeNode* cur = q.front();
          q.pop();
          // 访问 cur 节点，同时知道它所在的层数
          cout << "depth = " << depth << ", val = " << cur->val << endl;

          // 把 cur 的左右子节点加入队列
          if (cur->left != nullptr) {
              q.push(cur->left);
          }
          if (cur->right != nullptr) {
              q.push(cur->right);
          }
      }
      depth++;
  }
}

平衡二叉树

平衡二叉树是一种特殊的二叉搜索树，其左右子树的高度差不超过1。平衡二叉树的插入和删除操作会导致树的平衡性被破坏，需要通过旋转操作来维护平衡性。 使用递归算法将有序数组转化为平衡二叉树。

1
2
3
4
5
6
7
8
9
10

TreeNode* buildTree(vector<int> nums, int left, int right) {
    if (left > right) {
        return nullptr;
    }
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildTree(nums, left, mid - 1);
    root->right = buildTree(nums, mid + 1, right);
    return root;
}

二叉树的神奇操作

  • 二叉树的伸展 要将二叉树伸展成链表，可以使用前序遍历的方法。具体步骤如下：
  1. 如果当前节点为空，直接返回。
  2. 如果当前节点有左子树，将左子树插入到右子树的位置。
  3. 找到左子树的最右节点，将当前节点的右子树连接到这个最右节点的右子树上。
  4. 将当前节点的左子树设为空。
  5. 递归处理当前节点的右子树。

伪代码如下：

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

function flatten(root):
    if root is null:
        return

    if root.left is not null:
        // 将左子树插入到右子树的位置
        temp = root.right
        root.right = root.left
        root.left = null

        // 找到左子树的最右节点
        current = root.right
        while current.right is not null:
            current = current.right

        // 将右子树连接到左子树的最右节点的右子树上
        current.right = temp

    // 递归处理右子树
    flatten(root.right)

这个算法的时间复杂度是 O(n)，其中 n 是二叉树的节点数。

二叉树三种的遍历特点和应用

知道三种遍历中的中序和其他任意一种可以唯一确定一棵二叉树。前序遍历和中序遍历可以唯一确定一棵二叉树，后序遍历和中序遍历也可以唯一确定一棵二叉树。

  • 前序遍历：根+左+右；
  • 中序遍历：左+根+右；
  • 后序遍历：左+右+根。

所以如果知道中序可以知道左右子树，知道前序或后序可以知道根节点如何递归的分布。

Leetcode 105、106

对称二叉树

我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

1
2
3
4
5
6
7
8
9

    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }

    bool check(TreeNode* a, TreeNode* b) {
        if(!a || !b) return a==b;
        if(a->val != b->val) return false;
        return check(a->left, b->right) && check(a->right, b->left);
    }

二叉树的直径

本质就是找树的深度，然后在遍历的过程中记录左子树深度+右子树深度+1的最大值。树的深度为左右子树的深度的最大值 + 1；最大路径是左右子树的深度之和 + 1。

1
2
3
4
5
6
7
8
9
10
11
12
13

    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 1;
        depth(root, ans);
        return ans - 1;
    }

    int depth(TreeNode* node, int& ans) {
        if (node == nullptr) return 0;
        int L = depth(node->left, ans);
        int R = depth(node->right, ans);
        ans = max(ans, L + R + 1);
        return max(L, R) + 1;
    }

检查二叉搜索树

注意要保证左子树中不出现小于根节点的值，右子树中不出现大于根节点的值。

1
2
3
4
5
6
7
8
9

    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }

    bool isValidBST(TreeNode* root, long min, long max) {
        if (root == nullptr) return true;
        if (root->val <= min || root->val >= max) return false;
        return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);
    }

二叉搜索树的第k小的元素

二叉搜素树的中序遍历的结果是有序的，中序遍历，当计数为0时直接返回；

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int ans = -1;
        find(root, k, ans);
        return ans;
    }

    void find(TreeNode* root, int& k, int& ans) {
        if(!root) {
            return;
        }
        find(root->left, k, ans);
        if(--k == 0) {
            ans = root->val;
            return;
        } 
        find(root->right, k, ans);
    }
};

路径之和III

最近公共祖先

alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);

        if((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }

求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

简单回溯

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
35
36
37

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        vector<int> cur;
        // 注意层级过多时，int类型可能不够
        long ans = 0;
        count(root, cur, ans);
        return ans;
    }

    // 递归函数: 需要一个容器来储存数字
    void count(TreeNode* node, vector<int>& cur, long& ans) {
        if(!node) return;
        if(!node->left && !node->right) {
            // leaf node
            cur.push_back(node->val);
            ans += countInVec(cur);
            cur.pop_back();
            return;
        }

        cur.push_back(node->val);
        if(node->left) count(node->left, cur, ans);
        if(node->right) count(node->right, cur, ans);
        cur.pop_back();
    }

    int countInVec(vector<int> nums) {
        long i = 1, res = 0;
        std::reverse(nums.begin(), nums.end());
        for(auto num : nums) {
            res += num * i;
            i *= 10;
        }
        return res;
    }
};

二叉搜索树的迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
  • int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

思路：可以用栈的思想来完成中序遍历的过程。从根节点开始，依次入栈，方向是左子树。这样左子树在栈顶，根节点在栈底，实现中序遍历的先左再根。然后每弹出一个节点，判断其有没有右节点，有同上面的过程依次把右子树的左子树入栈。这样就实现根后右。

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

 // 本题使用栈解法、中序遍历的特点是前中后，先将根节点及其左孩子推入栈，推出时就是左-》中，再退出每个节点时判断有没有右子树，有也相同道理推入，这样就是左-》中-》右
class BSTIterator {
public:
    std::stack<TreeNode*> q;
    BSTIterator(TreeNode* root) {
        while(root) {
            q.push(root);
            root = root->left;
        }
    }
    
    int next() {
        if(!hasNext()) {
            throw runtime_error("No more elements.");
        }
        auto cur = q.top();
        int res = cur->val;
        q.pop();

        if(cur->right) {
            cur = cur->right;
            while(cur) {
                q.push(cur);
                cur = cur->left;
            }
        }
        return res;
    }
    
    bool hasNext() {
        return !q.empty();
    }
};

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

思路：我们知道，一个满的完全二叉树的节点个数是2^h - 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    // 暴力解法就是遍历法，这里不使用这个解题思路
    // 这里根据完全二叉树的性质来减少遍历次数，这里可以判断根节点的左右子树的层数来判断哪个是完全二叉树哪个不是，当左右子树的深度相同时，左子树为完全二叉树；当左右子树深度不同时，右子树为完全二叉树。完全二叉树可以直接计算节点数，而非完全二叉树则需要遍历。
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int left = 0, right = 0;
        // check which is 完全二叉树
        if (level(root->left) == level(root->right)) {
            // left
            left = countFull(root->left);
            right = countNormal(root->right);
            return 1 + left + right;
        } else {
            // right
            left = countFull(root->right);
            right = countNormal(root->left);
            return 1 + left + right;
        }
        return 0;
    }

    void getLevel(TreeNode* root, int& level) {
        if (!root)
            return;
        level++;
        getLevel(root->left, level);
    }

    int level(TreeNode* root) {
        int level = 0;
        getLevel(root, level);
        return level;
    }

    int countFull(TreeNode* root) {
        int h = level(root);
        return std::pow(2, h) - 1;
    }

    int countNormal(TreeNode* root) {
        if (!root)
            return 0;
        return 1 + countNormal(root->left) + countNormal(root->right);
    }
};

二叉搜索树的第k大节点

中序遍历二叉搜索树的结果是个有序数组，但是升序还是降序取决于其是先遍历左节点还是先遍历右节点。先遍历左节点得到的是升序，先遍历右节点得到的是降序。所以我们可以先遍历右节点，然后计数，当计数到k时返回当前节点。

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int ans = -1;
        find(root, k, ans);
        return ans;
    }

    void find(TreeNode* root, int& k, int& ans) {
        if(!root) {
            return;
        }
        find(root->left, k, ans);
        if(--k == 0) {
            ans = root->val;
            return;
        } 
        find(root->right, k, ans);
    }
};

验证二叉搜索树

验证规则：左子树中不存在比根节点大的值，右子树中不存在比根节点小的值。所有的节点都满足这个规则，才能验证是二叉搜索树。迭代时传入最小节点和最大节点，如果当前节点比最小节点还小或者比最大节点还大就不是二叉搜索树。

1
2
3
4
5
6
7
8
9

    bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if(!root) return true;
        if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) return false;

        bool left = isValidBST(root->left, minNode, root);
        bool right = isValidBST(root->right, root, maxNode);

        return left && right;
    }
算法
This post is licensed under CC BY 4.0 by the author.