罗罗编程学习记录
本页内容 展开查看

02.4.1.2 BST 与平衡树

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历

02.4.1.2-001 二叉搜索树(BST)的性质是什么?

一句话结论

任意节点的左子树所有键小于该节点,右子树所有键大于该节点;左右子树也是 BST;中序遍历得到严格(或非严格)递增序列。

概念解释

  • 有序性:左 < 根 < 右。
  • 递归定义:子树同样满足。
  • 中序有序是核心推论。

原理流程

  1. 从根比较目标。
  2. 小走左,大走右。
  3. 每层缩小一半范围(平衡时)。

代码 / 图示

      5
    /   \
   3     7
  / \     \
 1   4     8
中序:1 3 4 5 7 8

常见误区

  • 误区:只要求左孩子小于根;正解:整棵左子树都要小于根。
  • 误区:BST 一定平衡;正解:可能退化成链。

追问

  • Q:重复键怎么存? A:按实现放左或右,约定一致。
  • Q:BST 支持范围查询吗? A:中序遍历区间节点。

02.4.1.2-002 BST 查找怎么做?

一句话结论

从根比较,目标小走左、大走右、相等命中;空指针未命中;平衡树 O(log n),退化链 O(n)。

概念解释

  • 每层排除一侧子树。
  • 比较驱动分支。
  • 未命中到空。

原理流程

  1. 根为空返回 null。
  2. 相等返回当前。
  3. 小查左,大查右。

代码 / 示例

public TreeNode searchBST(TreeNode root, int val) {
    while (root != null && root.val != val) {
        root = val < root.val ? root.left : root.right;
    }
    return root;
}

常见误区

  • 误区:未命中继续比较空节点;正解:先判空。
  • 误区:左右方向写反;正解:小左大右。

追问

  • Q:查找路径长度? A:树高 h。
  • Q:递归与迭代等价? A:是,迭代省调用栈。

02.4.1.2-003 BST 插入怎么做?

一句话结论

按查找路径走到空位,新节点挂在叶子位置;不改动已有节点;平衡 BST 插入后需维护平衡;普通 BST 平均 O(log n),最坏 O(n)。

概念解释

  • 插入位置:查找未命中的空位。
  • 保持有序。
  • 父节点记录挂接。

原理流程

  1. 比较定位插入方向。
  2. 走到空位置。
  3. 父节点挂新节点。

代码 / 示例

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}

常见误区

  • 误区:插入后重新平衡普通 BST;正解:普通 BST 不自动平衡。
  • 误区:相等值插入左子树不约定;正解:重复值规则需统一。

追问

  • Q:插入会改变中序有序吗? A:保持。
  • Q:迭代插入怎么记父节点? A:双指针跟随。

02.4.1.2-004 BST 删除节点怎么做?

一句话结论

分三类:叶子直接删;单孩子用孩子顶替;两孩子用右子树最左(或左子树最右)节点值替换,再删该后继节点;O(h) 时间。

概念解释

  • 叶子:无后继问题。
  • 单孩子:孩子上移。
  • 两孩子:找中序后继顶替。

原理流程

  1. 查找目标。
  2. 按孩子数量分支处理。
  3. 两孩子取右子树最左替换并删除后继。

代码 / 示例

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode succ = root.right;
        while (succ.left != null) succ = succ.left;
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
}

常见误区

  • 误区:两孩子直接拿右孩子顶替;正解:右孩子可能仍有左子树,需最左节点。
  • 误区:删除后继时忘记递归;正解:后继在右子树中删除。

追问

  • Q:前驱顶替可以吗? A:可以,左子树最右,对称方案。
  • Q:删除后平衡吗? A:普通 BST 不保证,平衡树需旋转。

02.4.1.2-005 验证 BST(LC 98)怎么做?

一句话结论

递归时携带上下界:节点值必须在 (low, high) 开区间内,左子树上界收紧为当前值,右子树下界收紧为当前值;O(n) 时间 O(h) 栈。

概念解释

  • 全局约束:不只父子比较。
  • 区间传递。
  • 相等按开区间处理重复。

原理流程

  1. 根区间无界。
  2. 左孩子上界 = 当前值。
  3. 右孩子下界 = 当前值,越界返回 false。

代码 / 示例

public boolean isValidBST(TreeNode root) {
    return check(root, null, null);
}
private boolean check(TreeNode node, Integer low, Integer high) {
    if (node == null) return true;
    if (low != null && node.val <= low) return false;
    if (high != null && node.val >= high) return false;
    return check(node.left, low, node.val) && check(node.right, node.val, high);
}

常见误区

  • 误区:只比较父子节点;正解:需整棵子树满足区间。
  • 误区:用中序非递减就一定合法;正解:配合结构,重复值规则一致。

追问

  • Q:中序迭代判有序? A:记录前一个值,当前必须大于前驱。
  • Q:节点值含 Integer 边界? A:用 Long 或 null 哨兵避免溢出。

02.4.1.2-006 为什么 BST 中序遍历是有序的?

一句话结论

中序按左根右访问,左子树全部小于根、右子树全部大于根,递归展开后序列即从小到大;这是 BST 有序性的直接体现。

概念解释

  • 左子树先于根。
  • 根先于右子树。
  • 递归拼接有序段。

原理流程

  1. 左子树中序有序。
  2. 根居中。
  3. 右子树中序有序,整体递增。

代码 / 图示

左段(小) → 根 → 右段(大)

常见误区

  • 误区:前序也有序;正解:前序根在前,不全局有序。
  • 误区:中序有序就证明 BST;正解:是必要条件,仍需区间验证结构。

追问

  • Q:降序序列怎么取? A:中序先右后左。
  • Q:第 K 小怎么定位? A:中序计数到第 K 个。

02.4.1.2-007 BST 的最近公共祖先(LC 235)怎么优化?

一句话结论

利用 BST 有序性:p、q 都小于当前走左,都大于当前走右,否则当前即分叉点 LCA;O(h) 时间,优于普通树 O(n) 后序。

概念解释

  • 分叉点:两目标分属两侧。
  • 有序比较直接定位。
  • 无需遍历全树。

原理流程

  1. 比较当前与两目标。
  2. 同侧则下移。
  3. 异侧或命中当前即 LCA。

代码 / 示例

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}

常见误区

  • 误区:套用普通树后序;正解:BST 可按值比较 O(h)。
  • 误区:p、q 大小未排序;正解:代码两侧分别比较,不依赖先后。

追问

  • Q:普通二叉树 LCA? A:后序递归,见二叉树综合题。
  • Q:目标不存在? A:题目保证两节点在树中。

02.4.1.2-008 有序数组转平衡 BST(LC 108)怎么做?

一句话结论

取中间元素作根,左半递归左子树,右半递归右子树;中点保证左右长度差 ≤1,树平衡;O(n) 时间 O(log n) 栈。

概念解释

  • 有序数组天然中序序列。
  • 中点均分。
  • 递归构造。

原理流程

  1. 区间取中点。
  2. 建根节点。
  3. 左右半区间递归。

代码 / 示例

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] a, int l, int r) {
    if (l > r) return null;
    int m = l + (r - l) / 2;
    TreeNode root = new TreeNode(a[m]);
    root.left = build(a, l, m - 1);
    root.right = build(a, m + 1, r);
    return root;
}

常见误区

  • 误区:取端点作根;正解:中点均分保证平衡。
  • 误区:偶数长度纠结中点选左还是右;正解:任选一侧中点,两侧高度差 ≤1,均满足平衡。

追问

  • Q:有序链表转 BST(LC 109)? A:中序构造或快慢找中点,O(n log n)/O(n)。
  • Q:构造结果唯一吗? A:偶数长度可有多种平衡形态。

02.4.1.2-009 BST 第 K 小元素(LC 230)怎么做?

一句话结论

中序遍历计数,第 K 个访问的节点即答案;迭代中序可提前终止;O(h + K) 时间 O(h) 栈。

概念解释

  • 中序第 K 个即第 K 小。
  • 计数到 K 停止。
  • 迭代避免遍历全树。

原理流程

  1. 一路向左压栈。
  2. 弹出计数。
  3. 第 K 个返回,否则走右。

代码 / 示例

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> st = new ArrayDeque<>();
    while (root != null || !st.isEmpty()) {
        while (root != null) { st.push(root); root = root.left; }
        root = st.pop();
        if (--k == 0) return root.val;
        root = root.right;
    }
    return -1;
}

常见误区

  • 误区:先收集全量中序再取;正解:可提前终止省时间。
  • 误区:K 从 0 计;正解:题目 K 从 1 起。

追问

  • Q:频繁查询第 K 小? A:节点维护子树大小,O(h)。
  • Q:第 K 大? A:反序中序(先右后左)。

02.4.1.2-010 BST 前驱和后继怎么求?

一句话结论

前驱是左子树最右节点,后继是右子树最左节点;无对应子树时沿查找路径取最近转折祖先;O(h) 时间。

概念解释

  • 前驱:中序前一个。
  • 后继:中序后一个。
  • 子树内极值或路径祖先。

原理流程

  1. 有左子树:前驱 = 左子树最右。
  2. 有右子树:后继 = 右子树最左。
  3. 否则沿路径回溯。

代码 / 图示

前驱:左子树一路 right
后继:右子树一路 left

常见误区

  • 误区:前驱就是左孩子;正解:左孩子的最右后代。
  • 误区:叶子节点无前驱后继;正解:可能是路径祖先。

追问

  • Q:删除两孩子节点用谁顶替? A:后继(右子树最左)。
  • Q:极值节点前驱后继? A:可能为空。

02.4.1.2-011 BST 迭代器(LC 173)怎么实现?

一句话结论

栈保存左链;next() 弹出栈顶后把其右子树左链压栈;hasNext() 判栈非空;平均每次 O(1),构造 O(h),空间 O(h)。

概念解释

  • 迭代中序的栈状态。
  • 懒加载:按需压栈。
  • 与中序迭代同构。

原理流程

  1. 构造压入根左链。
  2. next 弹出,处理右子树左链。
  3. 栈空即无下一个。

代码 / 示例

class BSTIterator {
    private final Deque<TreeNode> st = new ArrayDeque<>();
    BSTIterator(TreeNode root) { pushLeft(root); }
    private void pushLeft(TreeNode node) {
        while (node != null) { st.push(node); node = node.left; }
    }
    public int next() {
        TreeNode cur = st.pop();
        pushLeft(cur.right);
        return cur.val;
    }
    public boolean hasNext() { return !st.isEmpty(); }
}

常见误区

  • 误区:构造时遍历全树存列表;正解:栈懒加载省空间。
  • 误区:next 不压右子树;正解:弹出后补右链。

追问

  • Q:逆序迭代器? A:压右链,先右后左。
  • Q:平均 next O(1) 怎么理解? A:每节点入栈出栈各一次。

02.4.1.2-012 BST 两数之和(LC 653)怎么做?

一句话结论

中序得到有序数组后相向双指针找两数和;或双迭代器(前序/逆序)对撞;O(n) 时间 O(h) 空间(双迭代器)或 O(n) 数组。

概念解释

  • BST 中序有序。
  • 有序数组两数之和双指针。
  • 迭代器避免全量存储。

原理流程

  1. 中序生成有序序列。
  2. 左右指针相向。
  3. 和小左移,和大右移。

代码 / 示例

public boolean findTarget(TreeNode root, int k) {
    List<Integer> list = new ArrayList<>();
    inorder(root, list);
    int l = 0, r = list.size() - 1;
    while (l < r) {
        int sum = list.get(l) + list.get(r);
        if (sum == k) return true;
        if (sum < k) l++; else r--;
    }
    return false;
}

常见误区

  • 误区:在树上直接双指针;正解:先有序化。
  • 误区:允许同节点用两次;正解:两指针指向不同位置。

追问

  • Q:哈希表边遍历边查? A:O(n) 空间,通用二叉树也可用。
  • Q:双迭代器对撞? A:左迭代器前进、右迭代器后退。

02.4.1.2-013 平衡二叉树(AVL)为什么需要?

一句话结论

普通 BST 按有序序列插入会退化成链,查找 O(n);AVL 通过强制左右子树高度差 ≤1 保持 O(log n) 高,代价是插入删除时旋转维护平衡。

概念解释

  • 退化:有序插入成链。
  • 平衡约束:高度差。
  • 旋转:恢复平衡。

原理流程

  1. 插入后检查祖先高度差。
  2. 失衡按类型旋转。
  3. 维持高度差 ≤1。

代码 / 图示

普通 BST 有序插入:链状 O(n)
AVL:始终 O(log n) 高

常见误区

  • 误区:BST 天然 O(log n);正解:只有平衡时才是。
  • 误区:AVL 平衡条件是节点数相等;正解:高度差 ≤1。

追问

  • Q:红黑树也是平衡树吗? A:近似平衡,约束更松。
  • Q:AVL 适合读多写少? A:查找快,旋转维护成本高。

02.4.1.2-014 AVL 有哪几类旋转?

一句话结论

失衡分 LL(右单旋)、RR(左单旋)、LR(先左后右双旋)、RL(先右后左双旋);按插入路径判断失衡类型,旋转后子树高度恢复。

概念解释

  • LL:左子树左侧插入。
  • RR:右子树右侧插入。
  • LR/RL:两侧混合,需两次旋转。

原理流程

  1. 找到最低失衡节点。
  2. 判断插入位置类型。
  3. 对应旋转调整指针。

代码 / 图示

LL:右旋
RR:左旋
LR:左孩子左旋 → 根右旋
RL:右孩子右旋 → 根左旋

常见误区

  • 误区:所有失衡一次旋转解决;正解:LR/RL 需双旋。
  • 误区:旋转只改值;正解:改指针结构。

追问

  • Q:旋转后高度怎么更新? A:按子树高度重算。
  • Q:面试要手写 AVL 吗? A:通常讲清四类与原理,代码以红黑树概念为主。

02.4.1.2-015 红黑树有哪些性质?

一句话结论

节点红/黑着色,根与叶子(NIL)为黑,红节点的孩子必为黑,任一节点到其叶子的黑节点数相同;近似平衡,保证最长路径不超过最短两倍;增删需变色与旋转。

概念解释

  • 着色约束。
  • 黑高一致。
  • 近似平衡而非严格高度差。

原理流程

  1. 插入按红节点。
  2. 违反红黑规则则变色/旋转。
  3. 维护黑高。

代码 / 图示

性质:根黑 / 叶黑 / 红不连续 / 黑高相等

常见误区

  • 误区:红黑树是严格平衡;正解:近似平衡,路径可差一倍。
  • 误区:红节点可以有红孩子;正解:红孩子必须黑。

追问

  • Q:Java 哪些结构用红黑树? A:TreeMap/TreeSet 等,具体以 JDK 实现为准。
  • Q:红黑树 vs AVL? A:AVL 更严格、查找快;红黑树插入删除维护成本低。

02.4.1.2-016 BST 与哈希表怎么对比?

一句话结论

哈希表平均 O(1) 查找但无序;BST 查找 O(h) 且支持有序遍历、范围查询、前驱后继;需要有序性选 BST/平衡树,纯按键取值选哈希。

概念解释

  • 哈希:无序、常数平均。
  • BST:有序、对数级。
  • 范围与顺序能力。

原理流程

  1. 看是否需要有序遍历。
  2. 看是否需要最值/前驱后继。
  3. 选型。

代码 / 图示

按键取值:哈希 O(1)
范围/第 K 小:BST O(log n + k)

常见误区

  • 误区:BST 查找 O(1);正解:平衡后 O(log n)。
  • 误区:哈希也能有序输出;正解:需额外排序。

追问

  • Q:有序映射用什么? A:平衡 BST 或跳表。
  • Q:哈希冲突退化? A:见哈希表章节。

02.4.1.2-017 普通 BST 退化成链有哪些表现?

一句话结论

按递增或递减序列反复插入,树高等于节点数,查找/插入/删除退化为 O(n);表现为所有节点挂在同一侧;需要随机化或平衡结构规避。

概念解释

  • 单侧生长。
  • 高度 = n。
  • 每层无二分。

原理流程

  1. 有序插入。
  2. 新节点始终走同一方向。
  3. 链状退化。

代码 / 图示

插入 1 2 3 4 → 右链
查找 4:4 步 O(n)

常见误区

  • 误区:BST 复杂度恒为 O(log n);正解:最坏 O(n)。
  • 误区:随机插入就一定平衡;正解:期望较平衡,仍需结构保证。

追问

  • Q:工程中用什么 BST? A:红黑树等平衡实现。
  • Q:BST 如何随机化? A:随机打乱插入顺序只是缓解,不保证。

02.4.1.2-018 BST 题有哪些边界用例?

一句话结论

空树、单节点、左右斜链、重复值、相等边界值、目标等于根/叶子、区间极值;验证区间比较、空判与前驱后继缺失。

概念解释

  • 空与最短。
  • 退化链。
  • 等值与边界。

原理流程

  1. 空树返回默认。
  2. 斜链检查高度。
  3. 等值按开/闭区间口径。

代码 / 图示

null / [5] / 左链 / 右链
val = MIN/MAX

常见误区

  • 误区:区间比较用闭区间处理重复;正解:重复规则与题目一致。
  • 误区:极值节点未判空;正解:前驱后继可能为空。

追问

  • Q:含 Integer.MIN_VALUE? A:区间哨兵用 Long 避免溢出。
  • Q:单节点 LCA? A:节点自身即祖先。

02.4.1.2-019 BST 操作复杂度怎么汇报?

一句话结论

平衡 BST 查找/插入/删除 O(log n);普通 BST 平均 O(log n)、最坏 O(n);中序遍历 O(n);空间 O(h) 递归栈;AVL/红黑树维护旋转常数次。

概念解释

  • 高度决定操作步数。
  • 平衡树高度对数。
  • 遍历全量 O(n)。

原理流程

  1. 标注树高口径。
  2. 操作沿一条路径。
  3. 辅助空间按栈深。

代码 / 图示

平衡 BST:O(log n)
普通 BST:平均 O(log n),最坏 O(n)
中序:O(n) / O(h)

常见误区

  • 误区:删除两孩子节点 O(n);正解:沿路径找后继 O(h)。
  • 误区:红黑树操作 O(1);正解:查找 O(log n),旋转常数次。

追问

  • Q:BST 范围查询代价? A:O(log n + k),k 为命中节点数。
  • Q:有序数组构造 BST 复杂度? A:O(n),每节点一次。

02.4.1.2-020 BST 常见变体考点有哪些?

一句话结论

验证 BST、有序数组转树、第 K 小、LCA、前驱后继、迭代器、两数之和;核心都围绕中序有序与按值分叉两条主线。

概念解释

  • 有序性:中序。
  • 分叉:比较定位。
  • 综合:与递归/栈结合。

原理流程

  1. 判断题目是否利用有序。
  2. 选中序或比较路径。
  3. 套用对应模板。

代码 / 图示

有序类:中序
定位类:比较下钻
构造类:中点均分

常见误区

  • 误区:把普通树题强行按 BST 比较;正解:先确认树满足 BST。
  • 误区:变体题忽略重复值约定;正解:先明确等值归属。

追问

  • Q:BST 与链表转换? A:中序展开为双向链表,见结构变换题。
  • Q:区间求和 BST? A:按值范围剪枝遍历。