企业官网建设流程全解析

我到现在还记得第一次点开刷题平台上“二叉树1”专题时的感觉：题量密密麻麻，每道题看起来都差不多，但又都不一样。如果你已经把数组、链表、字符串这些线性结构刷得差不多，正打算进入树形结构，那这篇内容应该能帮你少走不少弯路。二叉树看起来只是一堆节点的组合，但它几乎是所有算法套路的中转站：递归、深度优先搜索、广度优先搜索、分治、回溯，甚至后面的动态规划，都能在二叉树里找到最朴素的版本。

这篇内容围绕“二叉树1”这个专题展开，我会把刷这部分题目之前必须想明白的几个基础问题讲透，再把高频题型按套路拆开讲，最后用我自己实际踩过的坑做一次完整复盘。适合的人群很明确：刚开始刷树、一写递归就头皮发麻的同学，以及想快速建立二叉树解题框架、而不是靠死背答案的人。

1. 为什么二叉树是算法题里的“基本盘”

先不说具体题目，先聊一个容易被忽略的问题：为什么所有刷题攻略都把二叉树当成重点项目？答案不是“树上题目多”这么简单，而是因为二叉树的逻辑结构决定了它是一系列高级算法的天然练习场。

1.1 从“一个出口”到“左右两条路”的思维转变

数组、链表这类线性结构，解题思维是“沿着一条路往前走”。链表里每个节点只有一个 next，你要考虑的无非是遍历、插入、删除、反转，本质上是顺序问题。可二叉树一旦出现，每个节点都有左右两个孩子，问题立刻从“一条路”变成了“怎么选择、怎么回头、怎么汇总”。

这种结构变化带来两个直接影响。第一，题目很容易在“顺序”上做文章：先看父节点还是先看孩子，左孩子和右孩子哪个先处理，处理完要不要把结果带回去。第二，很多操作开始需要定义“返回值”，因为树的问题到后面往往不是简单输出一条路径，而是要把左右子树的结果合并成一个整棵树的答案。

我见过不少同学在二叉树部分突然卡住，不是因为题目变难了，而是思维还没从线性结构切换过来。看到 root.left、root.right 就当成链表的 next 来用，结果逻辑越写越乱。其实只要意识到“左右两条路”天然适合用递归处理，很多题目就有了解法方向。

1.2 二叉树是练习递归最好的土壤

递归为什么难学？因为很多人第一次接触递归是在阶乘、斐波那契这种数学题里，递归调用的路径不够直观。二叉树就不一样，它的结构本身就是递归定义的：一棵树的左子树还是一棵树，右子树也还是一棵树。这个特性让“自己调用自己”这件事变得有据可依。

在二叉树里写递归，通常只有两种套路。一种是遍历型：从根出发，一路走到底，把沿途节点记下来，前序、中序、后序遍历都属于这一类。另一种是分解型：先递归算出左子树的结果，再递归算出右子树的结果，然后拼出当前节点的答案，求深度、判断平衡、重建二叉树都属于这一类。

把二叉树刷明白之后，再去接触图、树形题目、甚至某些动态规划，会发现它们的思路都可以套回到“遍历型”或“分解型”这两种框架里。这也是为什么我建议不要只背题，而是把每一道二叉树题归入这两种套路之一，理解它属于哪种，心里就有底了。

2. 刷题前必须想清楚的四个基础问题

很多人一上来就刷题，刷到中途发现每道题都要重新想很久，问题往往出在基础概念没理清。下面这四个问题，是在“二叉树1”专题里所有题目的公共地基。

2.1 遍历顺序到底在排什么

二叉树的遍历顺序，本质上是在决定“处理当前节点”这件事发生在什么时候。前序遍历是根左右，意味着先读当前节点，再去处理左子树和右子树；中序遍历是左根右，处理当前节点的时机夹在左右子树之间；后序遍历是左右根，先把孩子处理完再处理自己。

不同的遍历顺序对应不同的场景。前序适合在遍历过程中构建结构，比如复制一棵树；中序在二叉搜索树里就是天然的有序序列；后序适合需要先知道子树结果再决定当前节点的题目，比如计算高度。层序遍历是另一个维度，它按层推进，天然对应队列这种先进先出的结构。

我建议你刷每一道题之前先问自己：这题的答案是在“进节点之前”得到，还是在“离开节点之后”得到？想清楚这个问题，递归代码的放置位置就有了。

2.2 递归函数设计的三个要素

二叉树题的核心是递归。递归函数设计通常看三要素：参数、终止条件、单层逻辑。参数决定调用的时候传什么；终止条件决定什么时候停止下钻；单层逻辑决定当前节点这一层要做什么操作。

拿求最大深度举例。参数是一个节点 root；终止条件是 root 为空时返回 0；单层逻辑是“当前这棵树的高度等于左子树高度和右子树高度的较大者，再加 1”。用代码写出来就是：

def max_depth(root): if not root: return 0 left_depth = max_depth(root.left) right_depth = max_depth(root.right) return 1 + max(left_depth, right_depth)

很多初学者会犯一个错误：单层逻辑里想着要累加全局变量，或者试图在递归里同时维护多个状态。其实对于分解型题目，最好的做法就是让递归函数返回一个明确的值，上一层直接用这个值做合并。这样思路清晰，也不容易出 bug。

2.3 返回值与终止条件的配合

递归函数返回什么，和终止条件返回什么，必须是一套逻辑。如果返回值设计成 int，终止条件返回的就是数值起点；如果返回值设计成 boolean，终止条件返回的就是一个布尔状态；如果返回值是 TreeNode，终止条件通常就是 None。

这里最忌讳的是“拍脑袋设计返回值”。我见过有人写判断平衡树的时候，递归函数一会儿要返回高度，一会儿又要返回是否平衡，最后不得不搞一个全局变量来补救。这实际上是返回值设计没想清楚的表现。

判断平衡这类题目有个常用技巧：让递归函数返回高度值，但用“-1”表示“当前子树不平衡”。这样上层拿到 -1 就能立刻终止，不需要额外的布尔返回值：

def height(root): if not root: return 0 left_h = height(root.left) if left_h == -1: return -1 right_h = height(root.right) if right_h == -1: return -1 if abs(left_h - right_h) > 1: return -1 return 1 + max(left_h, right_h) def is_balanced(root): return height(root) != -1

这种设计的好处是返回值语义统一，终止条件的 0 和 -1 各自表达清晰的含义，不会在调用层产生歧义。

2.4 用“小例子推演”代替背模板

二叉树递归不好理解，很多人的应对方式是把代码背下来。但题目一变，模板就失灵了。我更建议的做法是：拿一棵只有两三层的小树，手动推演递归的调用过程。推演几次之后，你对“递归栈”会有非常直观的感觉。

举个例子，一棵最简单的三节点树，根是 1，左孩子是 2，右孩子是 3。调用 max_depth(1) 时，会先调 max_depth(2)，再调 max_depth(3)，每一层调用会压入栈，等最深的调用返回后再逐层回溯。

这个过程听起来枯燥，但亲手画一遍调用栈，理解“先递后归”的含义，比背十道题都有用。我到现在写递归，遇到没把握的地方，还会在心里默念：当前节点是谁、它的左子树返回了什么、右子树返回了什么、我应该拿它们做什么。

3. 二叉树1里掉进去过的六类题目

“二叉树1”专题里的题目看着多，其实归类之后会发现就那几种套路。下面这六类，几乎覆盖了第一部分的大多数题目。

3.1 纯遍历题：递归与迭代的平衡

前序、中序、后序遍历是最基础的题目，递归写法三五行就能搞定。前序遍历的递归版本可以这样写：

def preorder(root): if not root: return [] res = [] res.append(root.val) res.extend(preorder(root.left)) res.extend(preorder(root.right)) return res

递归版本好理解，但面试里经常被追问一句：“能不能不用递归？”这时就要掌握迭代写法。前序的迭代可以借助栈，因为栈是先进后出，而前序要求先处理根再处理孩子，所以入栈顺序要反过来，先压右孩子，再压左孩子：

def preorder_iter(root): if not root: return [] res = [] stack = [root] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

中序遍历的迭代稍微难一点，需要用栈模拟“一路向左”的过程；后序遍历则可以取巧，用前序的镜像来记。无论哪种写法，核心都是搞清楚栈的入栈顺序对应哪种遍历顺序。这一块建议把所有三种遍历的迭代写法都各写一遍，不要只写一种。

3.2 树的高度与平衡判断

高度和平衡这两道题是“二叉树1”里的常客，它们都是典型的分解型递归。上一节已经给了求高度的代码，判断平衡树的代码也给了。这里我想强调一个容易出错的点：判断平衡不能只检查根节点的左右子树高度差，还要保证每一棵子树都平衡。

很多第一次写这道题的人会写出类似这样的逻辑：根节点左右子树高度差小于等于 1，就返回 True。结果遇到下面这种树就翻车：根节点左右高度差不大，但左子树的内部已经有一个子树严重失衡。正确的做法是递归里同时判断“高度差”和“子树是否平衡”，或者用返回 -1 的优化写法，否则时间复杂度会退化成很高的级别。

3.3 对称与翻转：两棵树的比较艺术

翻转二叉树和对称二叉树是两个容易混淆的题目。翻转是把每个节点的左右孩子交换，这是单棵树上的操作，递归逻辑很直接：

def invert_tree(root): if not root: return None root.left, root.right = root.right, root.left invert_tree(root.left) invert_tree(root.right) return root

对称二叉树则不同，它要判断一棵树是否镜像对称，本质上是比较两棵树：根节点的左子树和右子树是否互为镜像。这里的关键是递归时怎么配对：左子树的左孩子要和右子树的右孩子比，左子树的右孩子要和右子树的左孩子比，这就是所谓的“外侧对外侧、内侧对内侧”：

def is_symmetric(root): if not root: return True return is_mirror(root.left, root.right) def is_mirror(a, b): if not a and not b: return True if not a or not b: return False if a.val != b.val: return False return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)

对称这道题特别适合检验你对“递归函数到底比较的是哪两个节点”的理解。我后面会专门复盘一次我在这道题上踩的连环坑，这里先提醒一句：不要把 is_mirror 和 is_symmetric 混在一起递归，它们是两个不同层面的函数。

3.4 路径与深度优先：全局累积的隐性陷阱

有一类题目是“求二叉树中从根到叶子的路径总和是否等于某个目标值”。这类题目依然可以用递归做，但要注意“传值”和“传引用”的区别。我推荐的写法是每一层传入一个累计变量，但不要修改全局数值，而是在回溯时自然恢复。

def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return root.val == target return has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val)

这段代码的核心技巧是用“target - root.val”的方式逐层向下传递，不需要额外维护累加值，自然就不存在回溯恢复的问题。如果换成维护全局变量累加，递归返回时要手动减回去，漏了减就是经典 bug。所以这类题目我建议优先使用“按新值传递”的写法，少用全局变量。

3.5 层序遍历与BFS：队列的节奏感

层序遍历是“二叉树1”里少有的不是靠递归为主打的题目，它的天然工具是队列。一次循环处理一层，先统计当前队列里的节点数，然后逐个弹出并处理，下一层的节点则边处理边加入队列：

from collections import deque def level_order(root): if not root: return [] res = [] q = deque([root]) while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res

这里有个细节值得说：for 循环的次数必须在循环体前固定下来，即 len(q) 要提前取好。如果在循环体里动态取 len(q)，会因为队列一直在追加新节点而把当前层和下一层混在一起。这题的变体也很多，比如“从右边看到的节点”本质上就是每层的最后一个元素；“最大宽度”则是记录每层节点的位置信息。学会了这个层序框架，这些变体就是小改。

3.6 构造与重建：用遍历序列还原一棵树

前面几类题都是从树出发得到序列，重建类题目反过来：给你两种遍历序列，要还原出树。最常见的组合是中序遍历加前序遍历，或者中序遍历加后序遍历。为什么必须包含中序？因为中序序列能帮我们确定左右子树的分界位置，而前序或后序则用来确定根节点。

思路很简单，用前序序列的第一个元素确定根节点，再在中序序列里找到这个根节点，它左边的部分就是左子树的中序范围，右边就是右子树的中序范围。前序序列剩余部分则按左子树长度切分即可：

def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder[0] root = TreeNode(root_val) idx = inorder.index(root_val) left_size = idx root.left = build_tree(preorder[1:1 + left_size], inorder[:idx]) root.right = build_tree(preorder[1 + left_size:], inorder[idx + 1:]) return root

初学者最容易犯的错误是切分前序遍历的区间时想当然，没有先算出左子树的长度。另外一个实操优化是：不要用切片，因为 Python 的切片会频繁创建新数组，数据量大的时候性能很差。实际面试中更稳的做法是维护四个下标，在原列表上划分区间，代码更啰嗦但效率更高。这种优化不是炫技，而是体现你真的理解区间边界。

4. 实测中的常见坑与排查链路

理论刷几道题没用，真正让你成长的是踩坑和排查的过程。这一部分我把自己在这个专题里最常遇到的四类问题完整的复盘一遍。

4.1 空指针的玄学：root 为 null 到底返回什么

二叉树题的终止条件，几乎都围绕“空节点”展开。但“空节点返回什么”不能固定成一套，而要看上层想拿它做什么。求深度的递归里空节点返回 0；判断空树是否为对称的递归里空节点返回 True；如果是判断一个节点是否存在，空节点又要返回 False。

我在实际写代码时发现，如果看到一道二叉树题突然不知道怎么定终止条件，就说明递归函数的返回值定义还没有明确。一个很实用的自查技巧是：把递归函数当成一个“回答问题的函数”，终止条件就是回答“如果这是一棵空树，答案是什么”。这样定出来的终止条件，逻辑上是自洽的。

4.2 返回值设计混乱：一个函数想做太多事

“二叉树1”里有一类题很容易贪心，比如想在一次递归里同时求出高度和是否平衡，于是函数返回值设计成了一个 int，又在函数外面放了一个 boolean 变量记录状态。结果代码能跑，但逻辑极为难看，而且一旦递归顺序变化，全局变量就可能被错误覆盖。

解决方案就是上面提到的：让递归函数只返回高度，用 -1 表示不平衡状态。这样想拿高度就拿高度，想判断平衡就去主函数里查返回的是不是 -1。一个函数只做一件事，看起来多写了几行，排查起来却省时间得多。这也是我在刷题后期最大的体会：好的代码不是最短的代码，而是语义最清晰的代码。

4.3 递归栈溢出或超时的典型场景

二叉树的递归深度等于树的高度，如果这棵树退化成一条链，比如每个节点只有右孩子，那递归深度就是节点数量，非常深的树会导致超时甚至栈溢出。遇到这种问题，思路通常有两个方向：一是把递归改成显式的栈迭代，二是重新设计递归逻辑，避免重复计算。

提到重复计算，“二叉树1”里就有一个典型：判断平衡树时，如果在递归里每次都调用单独的高度函数去计算左右子树高度，而不做剪枝或合并，那么高度会被重复计算很多次，数据一多就超时。优化方法就是让递归函数在计算高度的同时传递“是否平衡”的信息，也就是前面写的 -1 写法。掌握了这个，遇到类似重复计算问题就有了条件反射。

4.4 一次对称判断的“连环错”复盘

对称二叉树这题，我当初第一次写时连续错了好几次，过程特别典型。第一次我写的递归是直接比较 root.left 和 root.right 的值是否相等，结果当然不对：一棵树光左右孩子值相等，不代表子树内部是对称的。那个报错样例是一棵根为 1、左子树根为 2、右子树根也为 2 的树，但它左子树的左孩子和右子树的右孩子不对称，我当时只盯着左右根节点，完全没往下递归。

第二次我改成递归比较，却把“内侧与内侧比较”翻译错了，写成了比较 a.left 和 b.left、a.right 和 b.right。这样一改，原本对称的树反而被判成不对称，原本不对称的树可能会被放过。这次报错让我彻底明白：is_mirror 函数里比较的是两棵树，a 的左孩子要与 b 的右孩子配对，a 的右孩子要与 b 的左孩子配对。

第三次更离谱，我试图先调用翻转函数把左子树翻转，然后判断它和右子树是否相等。思路理论上没毛病，但翻转操作原地修改了原来的树，导致第二次判断时数据已经不对了。最后的正确写法就是开头的 is_mirror 双树递归版本。这三次连环错让我总结出一条重要经验：涉及树的比较，优先使用“同时传入两个节点”的递归，而不是通过修改原树去制造比较条件。

5. 把二叉树1刷透之后的下一步

刷完第一部分的题，不代表这件事结束，接下来有两件事值得认真做。

5.1 建立自己的模板库

刷到后面你会发现，大约八成的二叉树题都能套到少数几个模板里。我个人的做法是维护了三个基础模板：遍历模板（前序递归和迭代）、高度模板（返回 int 的递归）、层序模板（基于队列的 BFS）。遇到新题，先试着归入其中一个模板，再根据题目要求在模板上打补丁。

比如“判断路径总和”就是遍历模板的变体；“求每层平均值”就是层序模板的变体；“判断最小高度”就是高度模板的变体。模板库的价值在于让你在面对新题时有一个稳定的切入点，而不是每次都从零开始在大脑里搜索解法。建模板库不用追求形式，自己看得懂就行。

5.2 从“会写”到“会讲”

代码写出来只是第一步，面试或交流时你还要能把思路讲清楚。我建议每写完一道题，花一分钟在脑子里过一遍：递归函数的输入是什么，输出是什么，终止条件为什么这样写，单层逻辑做了什么。能把这四句话讲顺，你对题的理解才算闭环。

这一步特别适合用在刷题同伴之间：你讲一遍，对方能不能听着思路写出代码，是检验你讲解质量的好标准。如果你是一个人刷，也可以把讲解写进代码注释里，下次回看时省力不少。

最后说一个我个人的小习惯：每次写完一个递归函数，我都会在草稿纸上把“空树”的情况单独列出来看一遍。很多 bug 不是逻辑复杂，而是对空树的处理想当然。把这句话作为这个专题的收尾，希望你刷到下一部分时，已经不再害怕递归。