02.4.1.2 BST 与平衡树
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历
02.4.1.2-001 二叉搜索树(BST)的性质是什么?
一句话结论
任意节点的左子树所有键小于该节点,右子树所有键大于该节点;左右子树也是 BST;中序遍历得到严格(或非严格)递增序列。
概念解释
- 有序性:左 < 根 < 右。
- 递归定义:子树同样满足。
- 中序有序是核心推论。
原理流程
- 从根比较目标。
- 小走左,大走右。
- 每层缩小一半范围(平衡时)。
代码 / 图示
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)。
概念解释
- 每层排除一侧子树。
- 比较驱动分支。
- 未命中到空。
原理流程
- 根为空返回 null。
- 相等返回当前。
- 小查左,大查右。
代码 / 示例
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)。
概念解释
- 插入位置:查找未命中的空位。
- 保持有序。
- 父节点记录挂接。
原理流程
- 比较定位插入方向。
- 走到空位置。
- 父节点挂新节点。
代码 / 示例
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) 时间。
概念解释
- 叶子:无后继问题。
- 单孩子:孩子上移。
- 两孩子:找中序后继顶替。
原理流程
- 查找目标。
- 按孩子数量分支处理。
- 两孩子取右子树最左替换并删除后继。
代码 / 示例
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) 栈。
概念解释
- 全局约束:不只父子比较。
- 区间传递。
- 相等按开区间处理重复。
原理流程
- 根区间无界。
- 左孩子上界 = 当前值。
- 右孩子下界 = 当前值,越界返回 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 有序性的直接体现。
概念解释
- 左子树先于根。
- 根先于右子树。
- 递归拼接有序段。
原理流程
- 左子树中序有序。
- 根居中。
- 右子树中序有序,整体递增。
代码 / 图示
左段(小) → 根 → 右段(大)
常见误区
- 误区:前序也有序;正解:前序根在前,不全局有序。
- 误区:中序有序就证明 BST;正解:是必要条件,仍需区间验证结构。
追问
- Q:降序序列怎么取? A:中序先右后左。
- Q:第 K 小怎么定位? A:中序计数到第 K 个。
02.4.1.2-007 BST 的最近公共祖先(LC 235)怎么优化?
一句话结论
利用 BST 有序性:p、q 都小于当前走左,都大于当前走右,否则当前即分叉点 LCA;O(h) 时间,优于普通树 O(n) 后序。
概念解释
- 分叉点:两目标分属两侧。
- 有序比较直接定位。
- 无需遍历全树。
原理流程
- 比较当前与两目标。
- 同侧则下移。
- 异侧或命中当前即 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) 栈。
概念解释
- 有序数组天然中序序列。
- 中点均分。
- 递归构造。
原理流程
- 区间取中点。
- 建根节点。
- 左右半区间递归。
代码 / 示例
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 停止。
- 迭代避免遍历全树。
原理流程
- 一路向左压栈。
- 弹出计数。
- 第 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) 时间。
概念解释
- 前驱:中序前一个。
- 后继:中序后一个。
- 子树内极值或路径祖先。
原理流程
- 有左子树:前驱 = 左子树最右。
- 有右子树:后继 = 右子树最左。
- 否则沿路径回溯。
代码 / 图示
前驱:左子树一路 right
后继:右子树一路 left
常见误区
- 误区:前驱就是左孩子;正解:左孩子的最右后代。
- 误区:叶子节点无前驱后继;正解:可能是路径祖先。
追问
- Q:删除两孩子节点用谁顶替? A:后继(右子树最左)。
- Q:极值节点前驱后继? A:可能为空。
02.4.1.2-011 BST 迭代器(LC 173)怎么实现?
一句话结论
栈保存左链;next() 弹出栈顶后把其右子树左链压栈;hasNext() 判栈非空;平均每次 O(1),构造 O(h),空间 O(h)。
概念解释
- 迭代中序的栈状态。
- 懒加载:按需压栈。
- 与中序迭代同构。
原理流程
- 构造压入根左链。
- next 弹出,处理右子树左链。
- 栈空即无下一个。
代码 / 示例
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 中序有序。
- 有序数组两数之和双指针。
- 迭代器避免全量存储。
原理流程
- 中序生成有序序列。
- 左右指针相向。
- 和小左移,和大右移。
代码 / 示例
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。
代码 / 图示
普通 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:两侧混合,需两次旋转。
原理流程
- 找到最低失衡节点。
- 判断插入位置类型。
- 对应旋转调整指针。
代码 / 图示
LL:右旋
RR:左旋
LR:左孩子左旋 → 根右旋
RL:右孩子右旋 → 根左旋
常见误区
- 误区:所有失衡一次旋转解决;正解:LR/RL 需双旋。
- 误区:旋转只改值;正解:改指针结构。
追问
- Q:旋转后高度怎么更新? A:按子树高度重算。
- Q:面试要手写 AVL 吗? A:通常讲清四类与原理,代码以红黑树概念为主。
02.4.1.2-015 红黑树有哪些性质?
一句话结论
节点红/黑着色,根与叶子(NIL)为黑,红节点的孩子必为黑,任一节点到其叶子的黑节点数相同;近似平衡,保证最长路径不超过最短两倍;增删需变色与旋转。
概念解释
- 着色约束。
- 黑高一致。
- 近似平衡而非严格高度差。
原理流程
- 插入按红节点。
- 违反红黑规则则变色/旋转。
- 维护黑高。
代码 / 图示
性质:根黑 / 叶黑 / 红不连续 / 黑高相等
常见误区
- 误区:红黑树是严格平衡;正解:近似平衡,路径可差一倍。
- 误区:红节点可以有红孩子;正解:红孩子必须黑。
追问
- Q:Java 哪些结构用红黑树? A:TreeMap/TreeSet 等,具体以 JDK 实现为准。
- Q:红黑树 vs AVL? A:AVL 更严格、查找快;红黑树插入删除维护成本低。
02.4.1.2-016 BST 与哈希表怎么对比?
一句话结论
哈希表平均 O(1) 查找但无序;BST 查找 O(h) 且支持有序遍历、范围查询、前驱后继;需要有序性选 BST/平衡树,纯按键取值选哈希。
概念解释
- 哈希:无序、常数平均。
- BST:有序、对数级。
- 范围与顺序能力。
原理流程
- 看是否需要有序遍历。
- 看是否需要最值/前驱后继。
- 选型。
代码 / 图示
按键取值:哈希 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 4 → 右链
查找 4:4 步 O(n)
常见误区
- 误区:BST 复杂度恒为 O(log n);正解:最坏 O(n)。
- 误区:随机插入就一定平衡;正解:期望较平衡,仍需结构保证。
追问
- Q:工程中用什么 BST? A:红黑树等平衡实现。
- Q:BST 如何随机化? A:随机打乱插入顺序只是缓解,不保证。
02.4.1.2-018 BST 题有哪些边界用例?
一句话结论
空树、单节点、左右斜链、重复值、相等边界值、目标等于根/叶子、区间极值;验证区间比较、空判与前驱后继缺失。
概念解释
- 空与最短。
- 退化链。
- 等值与边界。
原理流程
- 空树返回默认。
- 斜链检查高度。
- 等值按开/闭区间口径。
代码 / 图示
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)。
原理流程
- 标注树高口径。
- 操作沿一条路径。
- 辅助空间按栈深。
代码 / 图示
平衡 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、前驱后继、迭代器、两数之和;核心都围绕中序有序与按值分叉两条主线。
概念解释
- 有序性:中序。
- 分叉:比较定位。
- 综合:与递归/栈结合。
原理流程
- 判断题目是否利用有序。
- 选中序或比较路径。
- 套用对应模板。
代码 / 图示
有序类:中序
定位类:比较下钻
构造类:中点均分
常见误区
- 误区:把普通树题强行按 BST 比较;正解:先确认树满足 BST。
- 误区:变体题忽略重复值约定;正解:先明确等值归属。
追问
- Q:BST 与链表转换? A:中序展开为双向链表,见结构变换题。
- Q:区间求和 BST? A:按值范围剪枝遍历。