树

本章题海战术

典型例题	leetcode题目	leetcode链接
二叉树的前序遍历	leetcode 144	https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
二叉树的中序遍历	leetcode 94	https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
二叉树的后序遍历	leetcode 145	https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
二叉树的层序遍历	leetcode 102	https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
二叉树的锯齿形层序遍历	leetcode 103	https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
二叉树的最大深度	leetcode 104	https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
二叉树的最小深度	leetcode 111	https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
翻转二叉树	leetcode 226	https://leetcode.cn/problems/invert-binary-tree/description/
最近公共祖先	leetcode 236	https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
验证二叉搜索树	leetcode 98	https://leetcode.cn/problems/validate-binary-search-tree/description/
对称二叉树	leetcode 101	https://leetcode.cn/problems/symmetric-tree/description/
二叉搜索树第 k 小元素	leetcode 230	https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
二叉搜索树的最近公共祖先	leetcode 235	https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
路径总和	leetcode 112	https://leetcode.cn/problems/path-sum/description/
路径总和 II	leetcode 113	https://leetcode.cn/problems/path-sum-ii/description/
路径总和 III	leetcode 437	https://leetcode.cn/problems/path-sum-iii/description/
从前序与中序遍历序列构造二叉树	leetcode 105	https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
将有序数组转换为二叉搜索树	leetcode 108	https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

树

面试官好～关于树相关的常用算法题，我从基础特性、核心遍历、高频题型、避坑要点四块来梳理，都是大厂面试出镜率最高的内容，我尽量说核心考点～

基础概念速览 💡

面试里 90% 的树题都围绕二叉树展开，最核心的两类变种必须吃透：

• 普通二叉树：每个节点最多 2 个子节点，无排序特性
• 二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值，中序遍历结果天然有序，这是解所有 BST 题的核心钥匙
• 平衡二叉树：左右子树高度差绝对值 ≤ 1，是 TreeMap 等底层实现的基础

给大家举个最经典的示例树（也是力扣高频题的样例）：

核心遍历算法（必手写）📝

毫不夸张地说：90% 的树算法题，本质都是在遍历的基础上加逻辑。遍历是打底的内容，面试基本必问手写。

1. 四种遍历方式与对应场景

遍历方式	遍历规则	上面示例树的结果	典型面试应用
前序遍历(leetcode 144)	根 → 左 → 右	[3,9,20,15,7]	复制二叉树、打印所有路径
中序遍历(leetcode 94)	左 → 根 → 右	[9,3,15,20,7]	验证 BST、求 BST 第 k 小元素
后序遍历(leetcode 145)	左 → 右 → 根	[9,15,7,20,3]	求树的高度、删除二叉树
层序遍历(leetcode 102)	从上到下、逐层遍历	[3,9,20,15,7]	求树的宽度、按层处理节点

2. 递归实现（三要素模板）

递归是最直观的写法，面试优先写递归，再聊迭代优化。所有递归遍历都遵循三要素：

1. 终止条件：当前节点为空，直接返回
2. 单层逻辑：处理当前节点的值
3. 递归下沉：递归遍历左、右子树

以前序遍历为例，核心 Java 代码：

void preorder(TreeNode root) {
    // 终止条件
    if (root == null) return;
    // 处理根节点（前序：根在最前面）
    System.out.print(root.val);
    // 递归左右子树
    preorder(root.left);
    preorder(root.right);
}

中序、后序只需要调换「处理根节点」的位置即可。

3. 迭代与层序实现

• 前 / 中 / 后序迭代：用栈手动模拟递归栈，避免递归深度过大导致栈溢出
• 层序遍历：用队列实现 BFS 思想，是求层相关问题的万能模板

层序遍历核心代码(leetcode 102)（分层输出）：

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 先存当前层节点数，避免分层错乱
        int size = queue.size();
        List<Integer> levelList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            levelList.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(levelList);
    }
    return res;
}

高频经典题型 ✅

1. 二叉树的最大 / 最小深度（leetcode 104/leetcode 111）

• 考察点：后序遍历、递归思维
• 解题核心：
  • 最大深度：当前节点高度 = max(左子树高度, 右子树高度) + 1
  • 最小深度：必须到叶子节点才算深度，单侧子树为空时不能直接取 min
• 易错点：最小深度直接套最大深度逻辑，单侧树会算出深度 1 的错误结果

2. 翻转二叉树（leetcode 226）

• 考察点：前序 / 后序遍历
• 解题核心：遍历每个节点，交换它的左右孩子
• 小梗：Homebrew 作者当年因为写不出这题被谷歌拒了，面试常拿来当开胃菜

3. 最近公共祖先 LCA（leetcode 236 🔥 超高频）

这道题是字节、阿里、美团的必考题，属于必须手撕的级别。

• 考察点：后序遍历、回溯思想
• 解题核心：
  • 1.递归向下找 p、q 节点，找到就立刻向上返回
  • 2.左右子树都返回了非空节点 → 当前节点就是最近公共祖先
  • 3.只有一侧非空 → 说明两个节点都在这一侧，继续向上返回

核心代码：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 左右都找到，当前就是祖先
    if (left != null && right != null) return root;
    // 哪边非空返回哪边
    return left != null ? left : right;
}

LCA 逻辑示意图：

4. 二叉搜索树 BST 专项

BST 是面试重灾区，所有题都围绕「中序遍历有序」这个特性出。

• 验证 BST（leetcode 98）：中序遍历，判断序列是否严格递增
• BST 第 k 小元素（leetcode 230）：中序遍历到第 k 个元素直接返回
• BST 的最近公共祖先（leetcode 235）：利用特性，比两个值都大就走左，比两个值都小就走右

5. 路径和系列（leetcode 112/leetcode 113）

• 考察点：前序遍历、回溯思想
• 解题核心：向下遍历累加路径和，到达叶子节点时判断是否匹配目标值；需要输出所有路径时，用「进栈 - 递归 - 出栈」的回溯模板

技术难点与避坑表 ⚠️

难点场景	常见踩坑点	解决方案
递归深度过大	节点数过多时栈溢出 StackOverflow	改用迭代法实现，面试先说明递归的边界风险
空节点处理	漏判 null 导致空指针异常 NPE	递归 / 迭代第一步先判空，养成肌肉记忆
BST 边界判断	用 Integer.MIN_VALUE 当初始值，刚好节点有最小值就出错	用 Long 类型存初始值，或用 prev 变量存前一个节点
最小深度计算	单侧无子树时误算深度为 1	必须判断左右都为空才是叶子节点，单侧空取另一侧深度
层序遍历分层	没提前存 size，导致分层错乱	进入 while 循环后，先记录当前层节点数 size 再遍历

面试答题小技巧 🎯

1. 拿到树题先灵魂两问：用什么遍历顺序？递归还是迭代？
2. 优先写递归版本，写对就拿 80% 的分，再主动聊迭代优化
3. 看到 BST 直接条件反射「中序遍历有序」，90% 的题都能迎刃而解
4. 涉及路径、祖先、高度的题，优先想后序遍历 —— 需要子树的返回值做判断，就得用后序

核心亮点代码合集 ✨

每段实现都标注了面试加分的优化设计，都是面试官常问的「有没有更优写法」的标准答案。

1. 二叉树遍历统一迭代模板（前(leetcode 144) / 中(leetcode 94) / 后序(leetcode 145)通用）

// 以前序遍历为例，中序/后序仅需调整节点入栈顺序，逻辑完全通用
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            // 【亮点1】空节点做访问标记，一套模板通吃三种遍历，彻底解决迭代写法记忆混乱
            // 前序：根左右 → 入栈逆序：右 → 左 → 根
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
            stack.push(node);
            stack.push(null); // 标记位：表示该节点已被访问，下次弹出直接收集结果
        } else {
            // 遇到标记位，弹出的下一个节点就是当前要收集的目标
            res.add(stack.pop().val);
        }
    }
    return res;
}

技术亮点：

• 用空节点做状态标记，完美模拟递归栈的访问流程，三种遍历写法完全统一，记忆成本极低
• 打破传统迭代法前 / 中 / 后序逻辑割裂的问题，面试讲清标记法思路，能体现对递归本质的深度理解
• 代码一致性强，不易写错，面试紧张时也能稳定输出

2. 层序遍历(leetcode 102)（分层输出・最优标准实现）

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    // 【亮点1】用LinkedList实现队列，兼容空值且入队出队效率稳定
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size(); // 【亮点2】提前锁死当前层节点数，是分层正确的核心，90%的候选人这里会出错
        List<Integer> levelList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            levelList.add(node.val);
            // 【亮点3】仅入队非空节点，减少无效循环，空间效率最优
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(levelList);
    }
    return res;
}

技术亮点：

• 提前缓存当前层节点数size，彻底避免队列动态增长导致的分层错乱，是分层遍历的灵魂写法
• 边界判断前置，空树直接返回，无多余循环操作
• 非空节点才入队，杜绝容器内的无效元素，空间复杂度达到理论最优

3. 二叉树最近公共祖先(leetcode 235)（LCA・极简满分版）

字节、阿里、美团必考题，该写法是最精简的标准答案

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 【亮点1】终止条件一步合并：空节点/找到目标节点直接返回，同时覆盖边界与递归出口
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 【亮点2】左右非空=当前为祖先，单侧非空向上传递，逻辑零冗余
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

技术亮点：

• 利用后序遍历天然的回溯特性，无需手动维护路径数组，时间复杂度 O (n)，空间复杂度 O (h)（树高）
• 代码极致精简，同时兼容「节点不存在」的边界场景
• 完美体现递归「子问题结果向上传递」的核心思想，是递归算法的经典范式

4. 验证二叉搜索树(leetcode 98)（BST・无边界 bug 版）

public boolean isValidBST(TreeNode root) {
    // 【亮点1】用Long存前置值，彻底规避节点值等于Integer边界值的经典错题
    long prevVal = Long.MIN_VALUE;
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        // 一路向左压栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        // 【亮点2】边遍历边判断，不存储完整序列，空间从O(n)优化到O(h)
        if (root.val <= prevVal) return false;
        prevVal = root.val;
        root = root.right;
    }
    return true;
}

技术亮点：

• 用Long.MIN_VALUE做初始值，完美避开节点值等于Integer.MIN_VALUE的边界 case，通过率 100%
• 迭代实现避免递归深度溢出，大树场景下稳定性更强
• 原地判断无需额外数组存储中序结果，空间复杂度优化一个量级

分场景技术难点与解决方案 🎯

按面试题型场景分类，每个难点都对应具体踩坑现象和可落地的解决方法。

场景分类	技术难点	踩坑现象	解决方案
递归通用场景	递归深度过大导致栈溢出	节点数过万的二叉树，递归遍历直接抛出StackOverflowError	1. 生产 / 大树场景改用栈模拟的迭代法 2. 面试主动说明：递归写法简洁但有深度限制，优先写递归再提迭代优化
全题型通用	空节点漏判导致 NPE	访问节点值、左右孩子时，未判空直接触发空指针异常	1. 递归 / 迭代入口第一步先做节点判空 2. 入栈 / 入队前先校验节点非空，杜绝空元素进入容器 3. 形成肌肉记忆：操作节点属性前，先确认节点不为 null
层序遍历场景	分层遍历节点数错乱	未提前缓存 size，遍历过程中队列持续加入新节点，导致分层完全错误	进入每层循环前，先用int size = queue.size()锁死当前层节点数，for 循环仅遍历 size 次
BST 专项场景	边界值判断失效	用Integer.MIN_VALUE做初始比较值，树中存在该值时直接误判	1. 用Long.MIN_VALUE作为初始前置值 2. 更稳妥写法：初始 prev 设为 null，第一个节点仅赋值不做比较
深度 / 高度场景	最小深度计算错误	直接照搬最大深度的 min 逻辑，单侧无子树的节点会被误算为深度 1	明确叶子节点定义：左右孩子都为空才是叶子 单侧为空时，深度 = 另一侧子树深度 + 1，不可直接取 min
非递归遍历场景	后序遍历迭代写法易出错	传统写法逻辑独立，容易和前序混淆，面试紧张时极易写错	采用「空节点标记法」统一模板，仅调整入栈顺序即可，无需单独记忆后序逻辑
路径和 / 回溯场景	路径结果重复 / 遗漏	回溯时忘记移除最后一个元素，导致路径累加错误	严格遵循「添加元素→递归子节点→移除元素」的对称回溯模板，进出操作一一对应
LCA 场景	节点不存在时逻辑错误	默认 p、q 都在树中，若其中一个不存在会返回错误结果	递归前先遍历一次树，确认两个节点均存在；或在递归中增加存在性标记位

面试答题加分技巧 💡

1. 写代码前先讲思路：先说遍历方式、时空复杂度，再动手写，面试官会认为你思路清晰、成竹在胸
2. 写完主动提边界：比如递归的栈溢出风险、BST 的边界值问题，主动说出来比面试官追问加分更多
3. 优化思路递进：先写递归版（速度快、不易错），再主动补充迭代版的优化点和适用场景，体现思考深度

真实面试模拟

真实面试模拟

面试官 👨‍💼：

你好，今天我们来聊一聊二叉树相关的算法题。先热个身，二叉树的前序遍历(leetcode 144)你能写一下吗？递归和迭代两种方式都写一下。

候选人 🧑‍💻：

没问题。递归版本很简单，根->左->右的顺序，三行代码搞定。

public void preorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

迭代版本的话，我用一个栈来模拟递归调用栈，核心是先压右子节点，再压左子节点，因为栈是后进先出。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

面试官 👨‍💼：

好，那 中序遍历的迭代(leetcode 94) 怎么写？这个和前序不太一样吧。

候选人 🧑‍💻：

是的，中序是左->根->右，需要用一个指针cur一路向左走到尽头，然后再回溯。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {   // 一路向左
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        res.add(cur.val);      // 访问根
        cur = cur.right;       // 切到右子树
    }
    return res;
}

面试官 👨‍💼：

不错。那有没有办法只使用O(1)的额外空间完成遍历？你听过Morris遍历吗？

候选人 🧑‍💻：

听过，Morris遍历利用叶子节点的空闲右指针，指向自己的后继节点，从而实现不用栈的遍历。不过大厂面试里一般问到就说个思路就行，不会让现场写完整代码，但它的核心就是找前驱节点、建立线索、还原指针。

面试官 👨‍💼：

了解。接下来我们看层序遍历(leetcode 102)，也是BFS。怎么把二叉树一层一层输出成一个列表？

候选人 🧑‍💻：

用队列，每次先记录当前队列的size，这个size就是本层节点的数量，然后循环处理。这样就能分层。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

面试官 👨‍💼：

很好。如果我要你蛇形层序遍历(leetcode 103)呢？也就是第一行从左到右，第二行从右到左，交替进行。

候选人 🧑‍💻：

那我可以加一个布尔标记leftToRight，如果当前层需要从右到左，我可以在level列表里使用头插法，或者事后Collections.reverse。头插法更省事：

// 在for循环内，根据标记选择 add 或 add(0, val)
if (leftToRight) level.add(node.val);
else level.add(0, node.val);

面试官 👨‍💼：

理解。再看一个常见题：二叉树的最大深度(leetcode 104)。

候选人 🧑‍💻：

递归一行：

public int maxDepth(TreeNode root) {
    return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

面试官 👨‍💼：

那如何判断一棵树是平衡二叉树(leetcode 98)？

候选人 🧑‍💻：

平衡二叉树要求任意节点的左右子树高度差不超过1。我可以自底向上返回高度，并用-1作为不平衡标记，避免重复计算高度。

public boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}
private int getHeight(TreeNode node) {
    if (node == null) return 0;
    int left = getHeight(node.left);
    if (left == -1) return -1;
    int right = getHeight(node.right);
    if (right == -1) return -1;
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}

面试官 👨‍💼：

对称二叉树(leetcode 101)的判断呢？

候选人 🧑‍💻：

定义一个辅助函数，判断两棵树是否互为镜像。对称二叉树就是根节点的左右子树互为镜像。

public boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}
private boolean mirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}

面试官 👨‍💼：

接下来我们看路径总和(leetcode 112)/(leetcode 113)系列。给一个二叉树和一个目标和，问是否存在一条从根到叶子的路径总和等于目标和。

候选人 🧑‍💻：

标准的DFS减法思路，每次递归用目标和减去当前节点值，到叶子时检查是否刚好减到0。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return hasPathSum(root.left, targetSum - root.val) 
        || hasPathSum(root.right, targetSum - root.val);
}

面试官 👨‍💼：

如果路径不需要从根开始，也不需要在叶子结束，只要连续向下走，求总和等于target的路径总数呢？这题你怎么解？

候选人 🧑‍💻：

这是“路径总和 III(leetcode 437)”。我用前缀和+回溯。维护一个map记录从根到当前节点路径上各前缀和出现的次数，对于当前节点，看curSum - target在map里出现多少次，就多了多少条合法路径。然后再递归左右子树，最后回溯恢复map。

我画个图辅助说明：

假如路径是 10 → 5 → 3 → 3，前缀和分别是 10, 15, 18, 21，target=8，那么对于当前节点（最后一个3），我们找 21-8=13 是否在前缀和中出现过。这里13没出现过，所以没有以当前节点结束的路径。

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);
    dfs(root, 0L, targetSum, prefix);
    return count;
}
private void dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
    if (node == null) return;
    cur += node.val;
    count += prefix.getOrDefault(cur - target, 0);
    prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
    dfs(node.left, cur, target, prefix);
    dfs(node.right, cur, target, prefix);
    prefix.put(cur, prefix.get(cur) - 1); // 回溯
}

面试官 👨‍💼：

好，前缀和这个思路很清晰。我们换个方向，根据前序和中序遍历构造二叉树(leetcode 105)，这个能做到吗？

候选人 🧑‍💻：

可以。关键就是前序的第一个元素是根，在中序里找到这个根的位置，左边就是左子树，右边就是右子树。用一个HashMap存中序的值到索引的映射，避免每次循环查找。

public TreeNode buildTree(int[] pre, int[] in) {
    Map<Integer, Integer> inMap = new HashMap<>();
    for (int i = 0; i < in.length; i++) inMap.put(in[i], i);
    return helper(pre, 0, pre.length - 1, in, 0, in.length - 1, inMap);
}
private TreeNode helper(int[] pre, int pS, int pE, int[] in, int iS, int iE, Map<Integer, Integer> map) {
    if (pS > pE) return null;
    TreeNode root = new TreeNode(pre[pS]);
    int idx = map.get(root.val);
    int leftSize = idx - iS;
    root.left = helper(pre, pS + 1, pS + leftSize, in, iS, idx - 1, map);
    root.right = helper(pre, pS + leftSize + 1, pE, in, idx + 1, iE, map);
    return root;
}

面试官 👨‍💼：

有序数组转平衡二叉搜索树(leetcode 108) 呢？

候选人 🧑‍💻：

每次选数组中间元素作为根，左右两边递归构建，自然就是平衡的。

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

面试官 👨‍💼：

最后问一个经典的：二叉树的最近公共祖先(leetcode 236)。先说说普通二叉树的情况。

候选人 🧑‍💻：

递归思想，从根往下找：

• 如果当前节点是null或是p、q之一，就直接返回当前节点；
• 递归左右子树；
• 如果左右都不空，说明p和q分布在两侧，当前节点就是LCA；
• 如果只有一边非空，那一边的返回值就是LCA。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

面试官 👨‍💼：

那如果是 二叉搜索树(leetcode 235) 呢？

候选人 🧑‍💻：

利用BST的性质，如果p和q的值都小于当前节点，就递归左子树；都大于就递归右子树；否则当前节点就是分岔点，直接返回。

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

面试官 👨‍💼：

非常好 👍，关于树的算法题你掌握得很扎实，尤其是递归的思维和模板迭代都能写出来，复杂度分析也都在点上。这些题目覆盖了树的大部分考点，回去可以再巩固一下后序遍历的迭代写法，那个用双栈会好写一点。今天就到这里，谢谢。

候选人 🧑‍💻：

谢谢面试官，后序迭代我下去再写一遍，用 栈+prev指针 的方法也可以。感谢您的指点 😄

🧩 一、核心代码片段 & 技术亮点

1. 前序(leetcode 144)/中序迭代遍历(leetcode 94) —— 栈模拟递归

亮点：徒手写出无 Bug 的迭代，体现了对系统调用栈的深刻理解。

前序(leetcode 144)（根左右）：

Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    res.add(node.val);                 // 弹出即访问
    if (node.right != null) stack.push(node.right); // 先右后左
    if (node.left != null) stack.push(node.left);
}

中序(leetcode 94)（左根右）：

TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) {              // 一路向左压栈
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.pop();                 // 弹栈访问
    res.add(cur.val);
    cur = cur.right;                   // 进入右子树
}

2. Morris 遍历思路 —— O(1) 空间

亮点：面试中能清晰描述 Morris 原理，属于降维打击。利用空闲指针建立临时线索，完成后还原。

“找当前节点左子树的最右节点，将其右指针指向当前节点，这样不用栈就能回溯。”

3. 平衡二叉树判断(leetcode 98) —— “-1”标记法

亮点：自底向上一次遍历完成高度计算与平衡判断，杜绝 O(n²) 的重复计算。

private int getHeight(TreeNode node) {
    if (node == null) return 0;
    int left = getHeight(node.left);
    if (left == -1) return -1;
    int right = getHeight(node.right);
    if (right == -1) return -1;
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}

4. 路径总和 III(leetcode 437) —— 前缀和 + 回溯

亮点：打破“固定起点/终点”思维，用 curSum - target 查哈希表，O(n) 一次遍历解决所有可能路径。

Map<Long, Integer> prefix = new HashMap<>();
prefix.put(0L, 1);                    // 别忘了空路径
private void dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
    if (node == null) return;
    cur += node.val;
    count += prefix.getOrDefault(cur - target, 0);
    prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
    dfs(node.left, cur, target, prefix);
    dfs(node.right, cur, target, prefix);
    prefix.put(cur, prefix.get(cur) - 1); // 回溯清除
}

5. 前中序构造二叉树(leetcode 105) —— HashMap 定位根

亮点：用 Map 空间换时间，将寻找根节点从 O(n) 降到 O(1)，递归拆分左右区间。

int idx = inMap.get(root.val);           // 中序根位置
int leftSize = idx - inS;
root.left = helper(pre, pS+1, pS+leftSize, in, inS, idx-1, map);
root.right = helper(pre, pS+leftSize+1, pE, in, idx+1, inE, map);

6. LCA（最近公共祖先(leetcode 236)）递归妙解

亮点：几行代码解决看似复杂的问题，体现了对递归“从整体思考”的功力。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // 两侧都有
    return left != null ? left : right;             // 单侧有
}

BST 版本则利用节点值的大小关系，一行判断决定走向，更简洁。

⚠️ 技术难点 & 解决方案

技术难点	为什么难	💡 解决方案
迭代遍历时节点访问顺序	递归切换为迭代时，容易混淆压栈顺序和访问时机	记住“压栈反向”原则，前序先右后左；中序用指针一路向左 + 栈回溯
Morris 遍历实现	概念抽象，指针修改后需要复原，边界条件多	先会用语言清晰描述流程，再逐步编写；面试中多数情况讲清思路即过
平衡二叉树判断(leetcode 98)	直观做法是重复计算高度，O(n²) 容易超时	采用自底向上返回高度，-1 作为不平衡哨兵，一次遍历搞定
路径总和 III(leetcode 437)	路径不限定起点终点，暴力需枚举所有节点对，O(n²)	转化为前缀和问题，哈希表记录历史前缀和出现次数，配合回溯避免路径交叉
构造二叉树（前序+中序）(leetcode 105)	需要精确划分左右子树区间，下标容易写错	利用中序 Map 快速定位根，计算左子树长度，递归传参保持区间左闭右闭
LCA(leetcode 236) 递归理解	不理解递归函数“返回的是什么”，容易多写额外条件	明确函数定义：返回以 root 为根的子树里 p 或 q 的 LCA 或单个节点引用；利用返回结果是否为空来判断分布
递归边界条件	递归题第一步忘写 if (root == null) 导致空指针	养成肌肉记忆，先写递归终止条件，再考虑当前节点做什么

🌟 面试官的最后叮嘱

树的题目永远是递归 + 遍历的两板斧，迭代模板是必须背熟的。遇到变形题，先画一个简单的树跑一遍，思路自然就有了。不要怕递归，相信你的子调用能完成任务，你只需要处理好当前节点和子结果的关系。带着这些武器，下次面试树的环节你一定能稳稳拿下 💪😎