二叉树、BST 与分治

树是面试开始奖励「一种思维方式」而非「一个具体技巧」的地方。这节课里几乎每道树题都是四行递归——难点不在代码,而在于能不能把问题看成「先解两棵子树,再在当前节点合并」。本课从零开始建立这块肌肉:先把术语理清(Binary Tree、BST、Balanced、Complete 到底谁是谁),再讲三种遍历和它们的迭代 stack 模板,然后是那个能把 O(n log n) 解法拧成 O(n) 的「递归 vs 分治」区分,最后是坑掉最多候选人的 BST 不变式。

必须先说清楚的术语

写代码之前,这节课先把四个定义钉死,因为面试官拿它们当筛子——说混了,后面答得再对也可疑。

• Binary Tree(二叉树)——每个节点最多两个孩子,且无环。这个「无环、连通」的说法也正是它和 graph 的区别:树是一种特殊的连通无环图。
• Binary Search Tree(BST)——对每个节点,左子树里所有值都小于该节点、右子树里所有值都大于该节点。不变式约束的是整棵子树,不只是两个直接孩子——记住这个精确措辞。
• Complete / Full Binary Tree(heap 的形状)——Complete 树每一层都填满(可能除了最后一层),且最后一层尽量靠左堆(这正是 heap 能存进 array 的原因)。Full(或 proper)树更严:除叶子外每个节点都恰好有两个孩子。
• Balanced Binary Tree(平衡树)——对每个节点,左右子树高度差不超过 1。这正是 LC 110 要你验证的性质。

Depth 和 Height 都数「层数」——本课这些题里两者可以互换,只要保持一致(null 孩子贡献 0)就行。接下来是节点本身。让树一下子想通的心智模型是:树就是一条有两个 next 指针的 linked list。同样的纪律照搬:永远别丢 root 引用、dereference 前先 null-check、把 null 当成最关键的终止条件。

节点本身就是那三个显然的字段——一个 int val 加 left、right 两个引用——外加笔记点名的几个可选杠杆:需要往上走就加 parent 指针;N 叉树就把孩子换成 List<TreeNode> children;当扇出固定且小(比如 Trie 的 26 个字母)用普通 TreeNode[26] array 而不是 map,更快。

三种遍历

每种遍历都要访问 root、左子树、右子树——名字只是说明 root 什么时候相对子树被访问:

• Preorder(根左右):15 5 3 6 20 17 23
• Inorder(左根右):3 5 6 15 17 20 23 —— 升序,因为这是一棵 BST
• Postorder(左右根):3 6 5 17 23 20 15

这些数字来自那棵示例树——root 15,孩子 5 和 20,叶子 3、6、17、23。递归版(LC 144、LC 94、LC 145)完全一样,唯一区别是那行访问语句放在哪:挪一下就换 order。这就是全部诀窍。

void preorder(TreeNode root) {
    if (root == null) return;       // 终止条件:null 孩子
    visit(root.val);                // ← 放这里  → preorder
    preorder(root.left);
    // visit(root.val);             // ← 放这里  → inorder(BST 上升序)
    preorder(root.right);
    // visit(root.val);             // ← 放这里  → postorder
}

inorder 的位置值得刻进脑子:因为它把 BST 按升序吐出来,「这是不是合法 BST?」就变成「inorder 序列递增吗?」。要在遍历途中检查这一点,你得维护一个全局 prev 指针——局部变量每次递归调用都会重置,所以「上一个节点」必须活在递归之外。这个全局-prev 模式在下面一半的 BST 题里都会再出现,值得单独练成肌肉记忆。

迭代遍历:一个 stack 模板

面试官爱说「现在不用递归再写一遍」,因为这考的是你有没有理解「递归不过是一个显式的 stack」。有一个模板用同一套控制结构处理全部三种 order——你只改什么时候记录值。

public List<Integer> inorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    while (root != null || !st.isEmpty()) {
        if (root == null) {          // 左脊走到底 → 弹出后转向右
            root = st.pop();
            ans.add(root.val);        // inorder:回溯时才记录
            root = root.right;
        } else {                     // 一路把左脊压栈
            st.push(root);
            root = root.left;
        }
    }
    return ans;
}

其他两种都从这个骨架长出来。preorder 是在下行途中记录(else 分支里、root = root.left 之前)。postorder 有个漂亮的捷径:postorder 就是「根 → 右 → 左」的 preorder 反转一下——先按「右先于左」压栈建表,再 Collections.reverse(ans)(或者用 addFirst 往前插)。如果你不想绕这么多弯,最简单的迭代 preorder 更短:压入 root,然后循环——弹出、记录、并且先压 right,这样 left 会先被弹出来。

递归 vs 分治

这是本课的思维主干。两者都递归,但思路不同。普通递归是把一个「running result」穿过整条调用链(常借助全局)。分治(divide and conquer)则让每棵子树返回自己的答案,再在当前节点把两个答案合并——这正是 postorder 的形状。求 depth 是最干净的第一个例子:一个节点的高度是 1 + max(左高, 右高),而你必须等两个孩子都汇报完才能知道它。

// 精简版:节点上什么都不做时够用
public int getDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(getDepth(root.left), getDepth(root.right));
}

// 展开版:更推荐——「墙」给你留出处理或短路的位置
public int getDepth(TreeNode root) {
    if (root == null) return 0;
    int left  = getDepth(root.left);
    int right = getDepth(root.right);   // ── 墙:两棵子树都汇报完了 ──
    return 1 + Math.max(left, right);   // 在这合并;要加逻辑就写在这行之上
}

一行流很诱人,但笔记态度很坚决:把两个递归调用各占一行,和合并步骤之间留一道「墙」。一旦某道题需要检查两个子树的结果——比较、短路、累加一个全局最大值——你已经有了下手的接缝。这里每个递归都是 O(n):每个节点一次调用,每个节点只访问一次。

迭代版值得知道,但很少值得写。用显式 stack 做 DFS 要并行维护一个深度栈(节点和它的深度一起压,追踪 running max)。用 queue 做 BFS 对求深度最自然:一次处理一整层——取 size = queue.size(),恰好弹这么多节点、同时把它们的孩子入队,然后层数计数器加一。这种「逐层 BFS」是一整类题的骨架,到 第 8 课 会大放异彩。

LC 111 最小深度——null 孩子陷阱

把最大深度的递归直接换成 Math.min 是错的,而且 bug 很隐蔽。当一个节点只有一个孩子时,缺失的那侧返回 0,min(0, 某值) 塌成 0——于是报出一个无视了唯一真实路径的深度。修法是把 null 孩子当成「不是真分支」——某一侧是 0 就走另一侧,只有两个孩子都存在时才真取 min:return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;

平衡树(LC 110):O(n log n) → O(n)

照定义直译是对的但慢:在每个节点算左右子树高度、检查差 ≤ 1、再递归。能work,但 getDepth 本身是一次 O(n) 扫描,而你在 O(log n) 层里的每一层都调它——所以整体是 O(n log n)。一个小优化是剪枝:把高度差折进一个布尔,任何地方一失败就中止后续。

真正的修法更锋利,也是本课的招牌:让求高度的函数一职两用。让它正常返回高度,但一发现某子树不平衡就返回 -1。因为 -1 会向上传播——任何看到它的父节点也返回 -1——一次 post-order 就在 O(n) 里给出答案。

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

// 返回高度;一旦某子树不平衡就返回 -1
private int height(TreeNode root) {
    if (root == null) return 0;
    int left  = height(root.left);
    int right = height(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1)
        return -1;                    // 直接短路到顶
    return 1 + Math.max(left, right);
}

这正是上一节那道「墙」的回报:平衡判断恰好落在「两个孩子都汇报完」和「合并」之间的接缝上。「哨兵值向上传播」是你会反复复用的模式——直径、路径和、以及各种「这棵子树合不合法」的题,全是同一招。

对称家族:Invert、Symmetric、Same、Subtree

四道看着各不相同、其实是同一个想法的经典题——在一对节点上递归、调和它们的 base case。从最简单的开始。

LC 226 Invert Binary Tree——就是那道著名的「你连白板上翻转二叉树都不会」的题。分治让它只有三行:翻转两棵子树,然后交换它们。最后返回 root,才能让父节点重新接上被交换的孩子。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
    TreeNode left  = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;                       // 必须返回,父节点才能重新接线
}

// LC 101 — 用一个重载的双节点 helper 做镜像检查
public boolean isSymmetric(TreeNode root) {
    return root == null || isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;   // 都空 → OK
    if (a == null || b == null) return false;  // 只有一个空 → 不匹配
    if (a.val != b.val) return false;
    return isSymmetric(a.left, b.right) && isSymmetric(a.right, b.left);  // 镜像
}

LC 101 Symmetric Tree 把一个节点的左孩子和另一个的右孩子配对(镜像)。LC 100 Same Tree 是同一个 helper、只是把配对捋直——a.left 配 b.left、a.right 配 b.right。注意那三个 base case 每次都一样:都空(相等)、一个空(不等)、值不同(不等)。把这三连学会一次,你就写好了每道树比较题的一半。

LC 572 Subtree of Another Tree 是把「same tree」套进一次遍历:走遍大树的每个节点,问「以这里为根的子树和 t 相同吗?」笔记点名的那个微妙点——比较途中撞到 null 不一定就是不匹配,因为小树可以合法地比大树先结束;而这恰好就是 same-tree 的 base case 已经处理好的。最坏 O(m·n):每个节点都调一次 isSame。

Tweaked Identical(LintCode) 把对称推广了一层:每一层两棵子树可以要么直配(same-tree 配对)要么交叉配(symmetric 配对)。于是递推式把两种配对 OR 到一起。这个翻倍很贵——一个节点分裂出四条递归分支,得到 4^log n,而 4^log n = (2·2)^log n = 2^log n · 2^log n = n · n,所以复杂度是 O(n²)。能当场推出 4^log n = n²,正是那种随手一算就让面试官眼前一亮的分析。

验证 BST(LC 98)

最有教育意义的一道 BST 题,因为最显然的解法错得很有教育意义。那个诱人的做法——在每个节点检查 left.val < node.val < right.val——是错的,因为 BST 不变式管的是整棵子树,不是直接孩子。左子树深处的某个节点仍可能大于 root,而局部检查根本看不了那么远。有三个可靠解法:

1. inorder 到 list,再验证递增。用 inorder 把树拍平,确认每个元素严格大于前一个。正确、简单,O(n) 时间、O(n) 空间。
2. 往下传 (min, max) 区间。root 可以是任意值;它的左子树上界被 root 值卡住,右子树下界被卡住。下行时收缩窗口,任何越界的节点直接判负。这是最干净的递归——注意用 long 边界,才扛得住 Integer.MIN_VALUE / MAX_VALUE 作为节点值的情形。
3. 迭代 inorder + running prev。用前面那套 stack 模板,把每个弹出的值和上一个比——O(n) 时间、O(h) 空间,不用把整张 list 都物化出来。

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean helper(TreeNode root, long min, long max) {
    if (root == null) return true;
    if (root.val <= min || root.val >= max) return false;   // 越出允许窗口
    return helper(root.left, min, root.val)          // 左:把 max 卡到 root
        && helper(root.right, root.val, max);        // 右:把 min 抬到 root
}

把 BST 当搜索结构:范围查询与最近值

BST 的意义在于排序不变式让你能剪枝——和二分查找是同一种直觉,所以笔记把 BST 说成「带指针的二分查找」。两道题让它落地。

Search Range in BST(LintCode 11)——按升序打印 [k1, k2] 里所有 key。一个只打印区间内值的 inorder 遍历已经能在 O(n) 里做到,但用剪枝能更好:只有当前值仍可能大于 k1 时才递归左边,只有仍可能小于 k2 时才递归右边。落在窗口外的整棵子树永远不会被碰。

public int closestValue(TreeNode root, double target) {
    int closest = root.val;
    while (root != null) {
        if (Math.abs(root.val - target) < Math.abs(closest - target))
            closest = root.val;                 // 记录目前最优
        if (target < root.val) root = root.left;    // 直接剪掉另一半
        else if (target > root.val) root = root.right;
        else return root.val;                       // 精确命中
    }
    return closest;
}

LC 270 Closest BST Value——找离 target 最近的值。因为 BST 告诉你往哪走,你从不同时探两个孩子:每个节点更新一下目前最优,然后 target 更小就往左、更大就往右。这是一次 O(h) 走位——平衡树上 O(log n)——而在无序树上扫描要 O(n)。递归版精神完全一样;上面的迭代版只是省掉调用栈。

笔记里一个诚实的局限:找第 k 近的值在裸 BST 上并不干净,因为没有 parent 指针,你很难从 target 处向两个方向往外挪。务实答案是先把树 inorder 成 array 再在上面做——提醒你「对的数据结构」有时意味着把数据拷进另一种结构里。

刷题清单