0x11 二叉树

Review

  1. 2024-09-29 20:14

[!Summary]

一、Introduction #

  1. 144 二叉树前序遍历（根左右） ✅ 2024-09-29 DFS
  2. 94 二叉树中序遍历（左根右） ✅ 2024-09-29
  3. 145 二叉树后序遍历（左右根） ✅ 2024-09-29
  4. 102 二叉树层序遍历 #Medium BFS ✅ 2024-09-29
  5. 101. 对称二叉树 ✅ 2024-10-02
  6. 226. 翻转二叉树 ✅ 2024-10-02
  7. 110 平衡二叉树
  8. 104. 二叉树的最大深度 ✅ 2024-10-02
  9. 543. 二叉树的直径 ✅ 2024-10-02 ⭐️⭐️⭐️ 🚩
  10. 108. 将有序数组转换为二叉搜索树（平衡） ✅ 2024-10-02
  11. 98. 验证二叉搜索树 ✅ 2024-10-02
  12. 230. 二叉搜索树中第K小的元素 ✅ 2024-10-02
  13. 199. 二叉树的右视图 ✅ 2024-10-02
  14. 114. 二叉树展开为链表 ✅ 2024-10-02
  15. 105. 从前序与中序遍历序列构造二叉树

迭代实现后序遍历

function postorderTraversal(root: TreeNode | null): number[] {
    const res = [];
    const stack = [];
    let prev;

    while (root || stack.length) {
        while (root) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        if (!root.right || root.right === prev) {
            res.push(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }

    return res;
};
什么是二叉搜索树 #

二叉搜索树 (Binary search tree, BST) 是一种特殊的二叉树数据结构，它满足以下性质：

  • 左子树性质： 对于任意节点，其左子树中所有节点的值均小于该节点的值。
  • 右子树性质： 对于任意节点，其右子树中所有节点的值均大于该节点的值。
  • 子树性质： 任意节点的左、右子树也分别为二叉搜索树。
为什么使用二叉搜索树？ #
  • 高效的查找： 由于二叉搜索树的特性，我们可以通过比较待查找值与节点的值，快速地定位到目标节点。
  • 动态维护： 二叉搜索树支持动态插入和删除操作，可以随时保持树的结构有序。
缺点 #
  • 不平衡问题：在极端情况下，二叉搜索树可能退化为链表，导致查找效率下降。
  • 无法存储重复元素：如果要存储重复元素，需要进行一些特殊的处理。

二叉搜索树的中序遍历是升序序列

什么是平衡二叉搜索树 #

在二叉搜索树中，我们已经了解到，节点的左子树中所有节点的值都小于根节点，右子树中所有节点的值都大于根节点。但是，如果一棵二叉搜索树的结构过于倾斜，即一侧的子树远大于另一侧的子树，那么查找、插入、删除操作的效率就会大大降低，最坏情况下会退化为链表。

平衡二叉搜索树就是为了解决这个问题而出现的。它在二叉搜索树的基础上增加了一个平衡条件，保证树的左右子树的高度差不会超过某个特定的值。

为什么需要平衡？ #
  • 提高查找效率： 平衡二叉搜索树的查找时间复杂度可以保持在O(logN)，即使在最坏情况下也能保证较高的效率。
  • 避免退化成链表： 平衡条件可以有效地防止树的结构过于倾斜，从而避免查找效率的下降。
平衡二叉搜索树的种类 #

常见的平衡二叉搜索树有：

  • AVL树: 是一种严格要求平衡的二叉搜索树。它的每个节点的左右子树的高度差最多为1。
  • 红黑树: 是一种相对平衡的二叉搜索树。它通过给节点着色（红或黑）来维护平衡，平衡条件相对AVL树来说较为宽松。
平衡二叉搜索树应用场景 #
  • C++ STL中的map和set：底层实现就是基于红黑树的。
  • Java中的TreeMap和TreeSet：底层实现也是基于红黑树的。
  • 优先队列
  • 哈希表

Reference #