聊到二叉树，只要是准备技术面试的同学，大概率都绕不开它。我自己的感受是，二叉树在面试里的出现频率非常高，而且它不像动态规划那样让人摸不着头脑，也不像海量数据处理那样依赖工程经验，它处在“有点数据结构基础就能上手，但深挖下去能问出无数细节”的甜蜜位置。很多公司一面二面就爱出二叉树的中低难度力扣题，目的很直接：看看你递归熟不熟、DFS/BFS分不分得清、边界条件能不能一次写对。这篇内容我按自己复习时的心得来写，覆盖二叉树的核心知识点，配合力扣中低难度题目的 Java 解法，适合准备校招、跳槽、或者单纯想把树这块彻底理一理的人。
我会尽量写得接地气一点，每个题目都拆开讲，不光贴代码，还会解释为什么这么写、哪些地方容易翻车。你不需要事先刷完几百题，只要跟着思路走完一遍，再自己动手敲一遍，二叉树这块基本就有底了。
1. 为什么二叉树是面试里的“试金石”
1.1 一个结构覆盖了大半核心考点
二叉树这个结构很有意思，它表面上就一个节点加左右两根指针，却能引出递归、栈、队列、回溯、分治、双指针这些几乎所有高频考点。面试官如果准备一面，出一道二叉树题是最省事的选择，因为无论你想考基础还是考思维，都能在树这个框架里找到合适的切入点。
我见过很多同学刷题时会跳过树，觉得二叉树又不是什么高级数据结构，面试未必考。这个想法和实际情况差别很大。无论是应届生面试还是社招跳槽，二叉树的题目在高频题单里都占着可观的比例。更关键的是，树的题目往往能一题多问，面试官可以让你先写出递归版本，再追问迭代版本怎么处理，再问如果二叉树变成多叉树你会怎么改，甚至让你现场讲讲空间复杂度为什么是 O(h)。这种连环追问的套路，只有你真正理解原理，而不是背模板，才能接得住。
1.2 面试官在二叉树题目上到底看什么
很多人以为面试官只看结果，AC 了就万事大吉，代码错了就完蛋。实际上面试官更在意的是你思考问题和表达思路的过程。二叉树题尤其如此，因为它的解法通常不唯一，递归可以，迭代可以，甚至有的题还能用 Morris 遍历把空间压到 O(1)。面试官出题后，通常先观察你能否快速定位到正确的解法方向，再听你怎么解释复杂度，最后动手写代码，中间还会故意给边界条件挖坑。
比如他让你求二叉树最大深度，你说用递归，这当然对，但他接着问一句“如果树退化成一条链，会不会栈溢出”，这就牵扯到递归深度和系统栈的问题。如果你能答出“这里可以用显式栈模拟，把递归转化为迭代，空间复杂度是 O(n)”或者“实际刷题时递归深度一般不会成为瓶颈，但工程场景下要考虑”这种层次分明的话，分自然就拿到了。准备二叉树，我建议每个人都带着这种“多问自己一句”的习惯去练，不能只在编辑器里跑通用例就收工。
2. 预备知识：Java 中二叉树的表示与构建
2.1 顺序结构和链式结构，选择要看好场景
二叉树在计算机里有两种主流表示方式：顺序存储和链式存储。顺序存储就是把树的节点按层次放到数组里，父节点下标是 i 的话，左孩子是 2i+1，右孩子是 2i+2。这种写法在堆结构里很常用，比如优先级队列的内部实现，但在面试的算法题里用得不多，因为题目给你的通常是链式结构的颗立树，而且顺序结构在非完全二叉树上会浪费大量空间。
链式结构就是最经典的节点含左孩子、右孩子引用的写法。Java 中我们直接定义一个内部类或者独立类即可。面试的时候大部分力扣题默认就是这种结构，你需要非常熟悉它的定义，最好能闭着眼直接写出来，因为这属于基本功中的基本功，如果连 TreeNode 都要想半天，会给面试官留下基础不牢的印象。
2.2 手写 TreeNode 和建树工具
我们先看一下最常见的 TreeNode 定义。不同平台的题解里字段名可能稍有区别，有的用 left、right，有的用 leftChild、rightChild，但核心结构完全一致。
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }我这里特意把三个构造方法都写出来了。力扣里通常默认会提供这些构造器，但面试手写的时候，你只需要写最简单的一个带 val 的构造方法就够了。不过有个细节我得提一下，有些面试官会让你自己定义树节点，这时候如果你能主动把无参构造和全参构造也写出来，会显得你对 Java 的对象构造习惯很熟悉。
建树工具我个人建议准备一个。面试现场不一定让你建树，但你自己在本地调试的时候，总不能每次都手写一长串new TreeNode(...)然后手动left = ...。下面这个工具方法可以把形如[1,2,3,null,4,5]的数组转成一棵二叉树，用的是层序遍历的思路，遇到 null 就跳过，非常适合配合力扣的测试用例做本地验证。
public static TreeNode buildTree(Integer[] arr) { if (arr == null || arr.length == 0) { return null; } TreeNode root = new TreeNode(arr[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int index = 1; while (index < arr.length) { TreeNode node = queue.poll(); if (arr[index] != null) { node.left = new TreeNode(arr[index]); queue.offer(node.left); } index++; if (index < arr.length && arr[index] != null) { node.right = new TreeNode(arr[index]); queue.offer(node.right); } index++; } return root; }这里用Integer[]而不是int[]，是因为数组里会有 null 节点，基本类型数组装不了空值。这个细节虽然小，但如果面试时你恰好要用数组描述一棵树，它能体现你的细心程度。
2.3 一个直观的构建演示
光看不练容易觉得自己会了，实际一写就手生。我们拿一棵小树试一下，假设数组是[1,2,2,3,4,4,3]，这其实就是力扣一道经典题“对称二叉树”的测试用例。按上面的 buildTree 逻辑，先创建根节点 1，然后队列里放 1，index 从 1 开始，依次读 2、2、3、4、4、3。
手动走一遍流程：
- 弹出 1，读 arr[1]=2，作为左子节点；读 arr[2]=2，作为右子节点。
- 弹出左子节点 2，读 arr[3]=3 作为其左孩子，读 arr[4]=4 作为其右孩子。
- 弹出右子节点 2，读 arr[5]=4 作为其左孩子，读 arr[6]=3 作为其右孩子。
- 队列为空，结束。
构建完成后，这颗树以 1 为根，左右两边恰好镜像对称。平时做本地测试时，用这个工具会省很多时间。另外提醒一句，数组中间出现 null 时会跳过对应节点，但并不会让队列里的其他节点错位，因为每处理一个节点，我们固定消耗两个数组元素，这个逻辑在任何层级都成立。
3. 遍历四兄弟：递归与迭代的完整实现
3.1 递归：最自然、最容易写错的三种深度优先遍历
二叉树的深度优先遍历有三种：前序、中序、后序。所谓前中后，指的是“根节点”位置的先后顺序。前序是根左右，中序是左根右，后序是左右根。递归写法最大的好处是代码和遍历定义一一对应，基本不可能因为逻辑绕而写错，只要记住先处理谁、再处理谁就行。
public void dfs(TreeNode node) { if (node == null) { return; } // 这里写处理逻辑，就是前序 dfs(node.left); // 这里写处理逻辑，就是中序 dfs(node.right); // 这里写处理逻辑，就是后序 }很多初学者会把递归想得很玄乎，其实你可以把它理解为一个“不断把自己变小”的过程。每次递归调用都相当于把当前子树丢给同样规则的函数去处理，处理完左子树再回来处理右子树。这个思维一旦建立起来，后面做题会顺很多。
容易出错的地方也有两块。第一是忘了判空，第二是返回值没想清楚。尤其是判空，不管写前中后序还是写任何树相关的递归，第一步几乎都是if (node == null) return ...。有些同学会在递归里颠来倒去地把左右子树顺序搞反，这种错误往往和思路无关，纯粹是紧张导致的，写代码之前先默念一遍“根左右、左根右、左右根”就能避免。
3.2 迭代遍历：面试追问时最容易卡壳的环节
递归虽然好写，但面试官经常紧接着追问一句“你迭代怎么写”。这题背后考察的是你对系统栈的理解，说白了就是用自己申请的数据结构来模拟系统栈。
先看迭代前序。因为前序的顺序是根左右，所以我们可以先访问根节点，再把左子树全部压栈，左子树走完之后弹出节点转向右子树。这个思路很经典，代码也不长。
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { res.add(cur.val); stack.push(cur); cur = cur.left; } cur = stack.pop(); cur = cur.right; } return res; }迭代中序和前序长得非常像，区别只是把res.add(cur.val)的时机往后移到了从栈里弹出的时候。这个移动虽然只有一行之差，但含义完全不同：前序是在首次到达节点时就访问，中序是在左子树处理完后返回当前节点时访问。
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; }迭代后序稍微麻烦一点，因为后序是左右根，根节点最后访问。直接套用前序的循环结构会别扭，常见技巧是利用“前序的逆序”来间接构造后序。我们把前序遍历中“根左右”的顺序改成“根右左”，然后整体反转，就得到了“左右根”，正好是后序。实现上可以用一个 LinkedList，每次从头部插入结果，减少一次显式反转操作。
public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> res = new LinkedList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode cur = stack.pop(); res.addFirst(cur.val); if (cur.left != null) { stack.push(cur.left); } if (cur.right != null) { stack.push(cur.right); } } return res; }这里有个值得注意的点：因为我们用的是头插法，所以在入栈时先压左孩子再压右孩子，出栈顺序就会反过来，正好得到先右后左的访问顺序，再头插就变成了左右根。你要是想背模板，可以这样记忆：前序及逆前序的做法是通过“模拟系统栈”得到的，最终效果完全等价于递归，但空间上同样是 O(n)，只是不再占用系统调用栈。
3.3 层序遍历：BFS 的经典骨架
深度优先是一条路走到黑，层序遍历则是“逐层向下”的广度优先搜索。实现上离不开队列这个数据结构。每一轮先记录当前队列的长度，这个长度正是当前层的节点数，然后循环处理这么多个节点，处理完一层，再进入下一轮。这个“提前记录 size”的做法很关键，如果不先存 size，直接动态往队列里放节点，循环就会失控，因为你没法判断当前层和下一层的边界。
public 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> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); level.add(cur.val); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } res.add(level); } return res; }层序模板的用处远远超出“遍历一棵树”本身。后面会遇到像“二叉树的最大宽度”“二叉树的右视图”“锯齿形层序遍历”等中低难度题，底层都是这个模板的变体。所以宁可把这一段吃透，也不要急着疯狂刷题。真正理解 size 为什么必须在进入循环前取值，你就掌握了这一类题的共同解法。
4. 找规律：从遍历延伸出解题套路
4.1 DFS 递归模板与返回值设计
树的遍历只是起点，真正做题时我们发现，大部分二叉树题都能套一个非常相似的递归模板，差别在两点：子结果怎么合并、返回值表达什么语义。我们先看一个最常见的模板结构：
返回值类型 solve(TreeNode node) { if (node == null) { return 基本结果的默认值; } 返回值左 = solve(node.left); 返回值右 = solve(node.right); return 基于左右结果计算当前节点的结果; }这个模板的核心思想是“自底向上”的归并。你先假设左右子树都算好了结果，然后只考虑如何把这两个结果组合成当前节点的答案。为了确保这个模板有效，递归设计时你必须先想清楚“函数到底返回什么含义”。比如最大深度返回的是以某节点为根的子树的高度，验证二叉搜索树的中间过程返回的是“当前子树是否满足条件”，最近公共祖先返回的是“在当前子树中找到的目标节点是谁”。
我强烈建议所有人在写递归前，先口述一遍函数语义。我见过很多写不下去的同学，不是不会递归，而是压根没想清楚函数返回之后要交给上层什么信息。先把语义定下来，代码往往会自己顺出来。
4.2 自顶向下与自底向上的选择
树题目里有一个很经典的方向问题：你是要把答案从上往下传，还是从下往上一层层汇总？比如“路径总和”这种需要从根开始累计 targetSum 的题目，本质上就是自顶向下地传递一个更新后的目标值。而“最大深度”“判断平衡二叉树”就需要先拿到左右子树的结果，再在当前节点合并，属于自底向上。
怎么选方向？一个简单的判断标准：如果当前节点的答案能由左右子树的结果直接算出来，就用自底向上；如果当前节点的结果需要依赖从根到当前节点路径上的信息，就用自顶向下，通常配合一个参数传递来实现。
自底向上往往更符合递归直觉，因为递归本身就是先处理子树再返回。但有些题，比如“路径总和 III”，会要求枚举所有从上到下的路径，这时候纯靠自底向上会很绕，需要借助前缀和或回溯。我建议你在刷题时遇到这类问题别急着看题解，先自己按这个方向标准分析一遍，建立条件反射。
4.3 用遍历顺序说话的小技巧
三种深度优先遍历不只是代码模板，它们各自对应不同的题目倾向。中序遍历在二叉搜索树里特别重要，因为二叉搜索树的中序遍历结果是一个严格递增序列。很多验证类、查找类的 BST 题目，第一反应都应该想到中序遍历。
前序遍历通常用来做树的复制、序列化，因为根在前，你描述一棵树时天然是按根左右的顺序。后序遍历适合先处理子树再做决策的题目，比如删除节点、计算子树高度、最近公共祖先，因为你需要等左右子树的信息都返回后才能判断当前节点该怎么办。层序遍历则适合所有按层处理的问题，比如“二叉树的最小深度”“右侧视图”。
这个映射关系我整理成一句话：看到“递增/顺序”想中序，看到“根在前建树”想前序，看到“子树结果先知道”想后序，看到“一层一层来”想层序。
5. Easy 题实战：先把该拿的分稳稳拿到
5.1 最大深度：最简单的自底向上题
力扣原题编号 104，二叉树最大深度。这题几乎可以当作递归公式来背：空节点深度为 0，非空节点深度等于左子树深度和右子树深度的较大值再加 1。
public int maxDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }这段代码短小，但它把自底向上的思路体现得淋漓尽致。你也可以用层序遍历统计层数，代码会略长一些，但也能过。面试时我更推荐递归，因为解释起来最直白。不过要留意递归深度的边界，如果面试官追问，你可以补一句“不平衡的树最坏会退化成长链，递归深度 O(n)，工程环境中可能要改写成迭代”。
5.2 对称二叉树：双指针思想的雏形
力扣原题编号 101。题目要求判断一棵二叉树是否是关于镜像对称的。很多人的第一反应是把整棵树存下来再对比左右子树，其实更简单的做法是同时递归比较两个节点，一个向左时另一个向右。
public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } private boolean isMirror(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left); }这里的核心是把“镜像对称”转化为“p 的左子树要和 q 的右子树相等，p 的右子树要和 q 的左子树相等”。你可以把这个结构理解为一种“跨着走的双指针”，只不过指针在递归里变成了两个节点参数。代码里两个判空顺序也值得注意：先判两个都空，返回 true；再判一个空，返回 false。这个顺序不能反，否则空指针异常就在所难免。
5.3 翻转二叉树：递归交换的“送分题”
翻转一棵二叉树，意思是把每个节点的左右孩子都交换。这个操作之所以出名，是因为某位大佬在访谈中吐槽过自己被这题拒过，从此成了段子。但题本身难度不高，只要别真的在递归里直接交换引用就没事。
public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; }这里有一个非常容易犯的错误：有人会写成TreeNode temp = root.left; root.left = invertTree(root.right); root.right = invertTree(temp);这种写法其实也能通过，但逻辑上要小心，先覆盖了 root.left 再取 temp 就晚了。我更推荐先把左右结果存到局部变量，最后统一交换，这样思路最清晰，也不容易出空指针。
5.4 路径总和：回溯与递归状态的传递
力扣原题编号 112，判断一棵树里是否存在一条从根到叶子节点的路径，使得路径上所有节点值之和等于目标值。这题很适合展示减法的思维：不去维护一个累加的和，而是每次递归把 targetSum 减掉当前节点的值，到叶子节点时直接比较剩余值和叶子值的相等关系。
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); }这个写法的好处在于不需要额外维护一个求和变量，每次递归传递的都是更新后的目标值。要注意叶子条件的判断顺序是先判 root 为 null，再判左右孩子为空，否则节点为 null 时无法访问 val。另一个容易忽视的细节是这题目标值可能是负数，所以不能看到targetSum - root.val变成负数就剪枝，得老老实实走到叶子再判断。
6. Medium 题进阶：需要多想一步的经典题
6.1 验证二叉搜索树：边界条件与中序遍历
力扣原题编号 98，验证一棵树是不是二叉搜索树。二叉搜索树的定义是：左子树所有节点小于根节点，右子树所有节点大于根节点，而且左右子树本身也是二叉搜索树。很多人一开始写成只检查左孩子和右孩子，忘了还要保证左子树里所有节点都小于根，右子树里所有节点都大于根，这是这题最大的坑。
一种稳妥的解法是递归时传递上下界。根节点的取值范围是负无穷到正无穷，往左走时把上界收紧为当前节点值，往右走时把下界抬高为当前节点值。
public boolean isValidBST(TreeNode root) { return check(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean check(TreeNode node, long min, long max) { if (node == null) { return true; } if (node.val <= min || node.val >= max) { return false; } return check(node.left, min, node.val) && check(node.right, node.val, max); }这里用 long 而不是 int，是为了绕过节点值恰好等于 Integer.MIN_VALUE 或 MAX_VALUE 时的边界尴尬。如果你用 int 初始化上下界，一个值为 Integer.MAX_VALUE 的根节点会直接被判非法。这也是面试时很值得主动说出来的细节。
另一种常见解法是利用中序遍历。因为二叉搜索树中序遍历的结果一定严格递增，所以只需要在中序遍历中检查上一个值是否小于当前值。这个做法省去了上下界参数，但需要维护一个 prev 变量，写法上稍微隐晦一点。
public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; long prev = Long.MIN_VALUE; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); if (cur.val <= prev) { return false; } prev = cur.val; cur = cur.right; } return true; }这两种解法面试时最好都会。先用递归上下界版本把思路讲清楚，如果面试官问你“能不能不用递归”，再切换到中序迭代写法，会显得很扎实。
6.2 二叉树的最近公共祖先：自底向上的典型应用
力扣原题编号 236，最近公共祖先问题。所谓公共祖先，就是两个节点的共同祖先节点中离它们最近的那个。递归解法的思路并不复杂：如果当前节点为 null，或者当前节点就是 p 或 q，就直接返回当前节点；否则在左子树和右子树里分别找，如果两边都找到了，说明当前节点就是公共祖先，返回它；如果只有一边找到，那就把这边的结果继续向上传递。
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; }这个解法的精妙之处在于它同时处理了多种情况。如果 p 和 q 分别位于左右子树，当前节点就是答案；如果 p 是 q 的祖先，递归时遇到 p 就直接返回，不会再往下走，答案自然就是 p。理解这段代码的关键在于想清楚返回值到底代表什么，它是在当前子树中，p 或 q 的“找到结果”或“潜在公共祖先”。我在面试中聊过这题，面试官往往还会追问“如果树节点没有指向父节点的指针，你怎么办”。递归已经覆盖了这种场景，反而是如果有父指针，可以改成双指针向上走查找交叉点，那是另一道变体题。
6.3 二叉树的锯齿形层序遍历：BFS 加方向标志
力扣原题编号 103，要求按之字形逐层遍历。第一层从左到右，第二层从右到左，第三层再从左到右。其实就是在层序遍历模板的基础上加一个方向标志。只要用 LinkedList 来存储每一层结果，从左到右时从尾部添加，从右到左时从头部添加，就能规避频繁 reverse 带来的额外开销。
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int size = queue.size(); LinkedList<Integer> level = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); if (leftToRight) { level.addLast(cur.val); } else { level.addFirst(cur.val); } if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } leftToRight = !leftToRight; res.add(level); } return res; }LinkedList 的 addFirst 是 O(1) 操作，如果用 ArrayList 做 add(0, val) 就需要移动元素，复杂度会退化。这种细节虽然不影响通过，但能体现你是否对数据结构特性敏感。面试时如果不小心写成了 ArrayList 的 add(0, val)，被追问复杂度后如果能主动纠正到 LinkedList，也是一个加分项。
6.4 二叉树展开为链表：原地改造的考点
力扣原题编号 114，要把一棵二叉树展开成一条右指针链表，顺序等同于前序遍历。这题有两个层面的解法。第一种最简单的思路是先做一次前序遍历，把节点存到列表里，再重建出右链结构。这种解法很好想，但空间复杂度是 O(n)。
原地改造的方式更优雅。核心思路是：对于当前节点，如果它有左孩子，就让左子树的最右节点接到当前节点的右孩子上，然后把左孩子变成右孩子，左孩子置空，再继续处理下一个节点。这个操作做起来很像把一个链表中的节点重新串联。
public void flatten(TreeNode root) { TreeNode cur = root; while (cur != null) { if (cur.left != null) { TreeNode prev = cur.left; while (prev.right != null) { prev = prev.right; } prev.right = cur.right; cur.right = cur.left; cur.left = null; } cur = cur.right; } }面试时我建议先从“前序列表再重建”讲起，说出它的时间复杂度 O(n)、空间复杂度 O(n)，再引出原地算法，表示可以把空间优化到 O(1)。这题的关键是别在进入下一个节点后迷失方向，每次处理完左子树后，cur 会移动到原来左子树的根上，所以整个链表会天然保持前序顺序。
7. 高频坑点与现场经验
7.1 判空条件的顺序到底怎么设计
二叉树题目的第一道门槛就是判空顺序。大部分场景要先把node == null放前面，但如果你的递归语义里 null 有特殊含义，就要格外小心。比如在最近公共祖先题里，root == p || root == q必须放在递归调用之前判断，否则会陷入无限递归，因为 p 或 q 可能根本不在当前子树里。
另外，链式访问也容易在判空上翻车。root.left.left这种写法之前必须先确认 root 和 root.left 都不为空。有些人习惯在每行代码后面加判空，代码变得非常啰嗦，也不利于阅读。正确做法是提高递归的抽象层次，尽量让每层代码只操作当前节点和下一层节点，不要跨两层。
7.2 递归变迭代：栈的操作顺序容易反
从递归改成迭代时，最常见的错误是把压栈顺序搞反。因为栈是后进先出，如果你要模拟前序遍历“根左右”的顺序，压栈时应该先压右孩子再压左孩子，这样左孩子先出栈。但是中序迭代不能简单套用“先压右再压左”的思路，因为中序需要不断往左走到尽头，再往回弹栈转向右树，这个流程和压栈顺序的关系更隐蔽。
我建议你把三种迭代遍历的模板单独整理出来，考前反复默写几遍，直到不用想就能写出来。面试现场高度紧张，临场推导容易出错，还不如平时把肌肉记忆练好。
7.3 复杂度口径：别只说时间，不说空间
二叉树题目的复杂度讨论里，时间复杂度和空间复杂度是两个维度。时间复杂度比较容易，大部分题都是 O(n)，因为每个节点访问一次。空间复杂度就有讲究了，递归版本的空间主要消耗在系统栈上，最差 O(n)，平均 O(log n)；迭代版本显式申请的栈或队列同样是 O(n)，但要说明是额外空间。有些题的空间复杂度可以优化到 O(1)，比如 Morris 遍历，但那是进阶内容，面试时如果主动提一句“这块还能用 Morris 进一步优化”，会显得视野很开阔。
7.4 面试现场的时间分配与口头沟通
我建议把一道二叉树题控制在 15 到 20 分钟内。前 2 分钟确认题意和边界条件，比如“树为空怎么办”“目标值有没有负数”“节点值是 int 还是 long”。中间花 5 分钟设计解法和复杂度，如果面试官没反对，再动笔写代码。写完后一定要自己手动走一个简单用例，别等面试官来指出错误。
口头解释时不要只说结论，要用“我打算先……因为……”“这里主要的坑是……”这种带因果关系的表达。面试官在听的是你的思维链路，而不是背诵结论。还有个小技巧：拿到题先问一句“二叉树节点的构造是可用力扣默认的 TreeNode 吗”，这个提问本身就能体现工程意识。
8. 一周复习计划与题单速查表
8.1 建议的刷题顺序
如果你只有一周突击时间，我建议按这个节奏来。
一到两天先把遍历四兄弟吃透，递归前序、中序、后序、层序，再练三遍迭代版本，直到不看资料能写出来。然后每天集中做四到六道题，从简单题入手，最大深度、对称二叉树、翻转二叉树、路径总和，这些都是高频送分题，不能丢分。
中档题里优先做验证二叉搜索树、最近公共祖先、锯齿形层序遍历、展开为链表。这几道的思路各有代表性，分别覆盖上下界递归、自底向上合并、BFS 变体、原地链表重构。如果你时间更紧，至少确保验证二叉搜索树和最近公共祖先这两道能完全独立写出来，因为它们出现的概率实在太高。
剩下一天用来复习错题和复杂度分析。把刷过的题重新看一遍，确保每道题都能说出“为什么选择这个解法”和“空间复杂度怎么算”，而不是只看个代码。
8.2 知识点自查清单
我整理一个清单，你可以在考前做一次快速自测。每一行如果你能做到“不看题解直接写并讲清原理”，这一行的格子才算打勾。
| 知识点 | 对应题目思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 递归前中后序 | 三种顺序的访问时机 | O(n) | O(h)，h 为树高 |
| 迭代前中后序 | 显式栈模拟 | O(n) | O(n) |
| 层序遍历 | 队列 + 每层 size 快照 | O(n) | O(n) |
| 最大深度 | 自底向上合并 | O(n) | O(h) |
| 对称二叉树 | 镜像双递归 | O(n) | O(h) |
| 路径总和 | 自顶向下传 target | O(n) | O(h) |
| 验证 BST | 上下界递归或中序迭代 | O(n) | O(h) 或 O(n) |
| 最近公共祖先 | 自底向上返回值合并 | O(n) | O(h) |
| 锯齿层序 | BFS + 双向列表 | O(n) | O(n) |
| 原地展开 | 左子树最右节点连接 | O(n) | O(1) |
这里的 h 是树高，最坏可以到 n，所以不少题的“理论最差空间”其实是 O(n)。面试时如果面试官问最坏情况，一定要说明“最差会退化成链表，高度为 n”，这比只说 O(logn) 更严谨。
最后再分享一个小经验。很多人觉得二叉树题刷过一遍转头就忘，这很正常。真正能帮你记忆的不是刷更多题，而是每做一道题后花两分钟把这道题的“解法方向”和一道旧题关联一下。比如验证 BST 的中序思路，其实和“二叉搜索树中第 K 小的元素”是一路子；最近公共祖先的自底向上思路，和“判断二叉树是否包含某条从根到叶的路径”也是相通的。树这块题目看多了你会发现，真正核心的套路不超过十种，把套路吃透，远比自己闷头做一百道题更有用。
