企业官网建设流程全解析

LeetCode 树专题通关指南：一个中心、两个基本点、三种题型、四个概念与七个技巧

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇指南以 lucifer 在 leetcode 题解仓库中撰写的树专题为核心，系统梳理了树这一数据结构的全部刷题套路：从"树的遍历"这一个中心出发，延伸到 DFS 与 BFS 两个基本点，归纳出搜索、构建、修改三种题型，提炼出二叉搜索树、完全二叉树、路径、距离四个重要概念，并给出可落地的七个实操技巧。读完本文，你将掌握统一的二叉树遍历迭代写法、可套用的 BFS 模板、按题型分类的解题框架，以及从零构造与修改二叉树的完整方法论。

为什么树没有想象中那么难

很多人觉得树是一个很难的专题，实际上从数据上看并非如此。以 LeetCode 官方难度标签统计：树标签下的题目中，困难难度一共 14 道（其中还有 1 道标着树标签却是图论的题目），困难率约 13 / 175 ≈ 7.4%；排除上锁题目后困难的只有 9 道。从通过率看，只有不到三分之一的题目平均通过率在 50% 以下，绝大多数题目的通过率都在 50% 以上——作为对比，BFS 的平均通过率差不多是 50%，而二分法与动态规划的平均通过率约为 40%。

树之所以给人"难"的印象，往往是因为套路没有被归纳出来。本文用一个口诀**"一个中心，两个基本点，三种题型，四个重要概念，七个技巧"**来串联整个树专题，把散落的题目归入有限的模式之中。

树的基本概念与表示方法

树是一种非线性逻辑结构，是对现实世界中层次关系的抽象：家族族谱、公司组织架构、电脑文件夹结构、HTML 渲染的 DOM 结构，都属于树。树结构的基本单位是节点，节点之间的链接称为分支（branch），结构的开端称为根（root），根节点之外的节点称为子节点（child），没有链接到其他子节点的节点称为叶节点（leaf）。

每个节点可以用以下数据结构表示：

Node { value: any; // 当前节点的值 children: Array<Node>; // 指向其儿子 }

其他重要概念：

• 树的高度：节点到叶子节点的最大值就是其高度；
• 树的深度：高度与深度方向相反——高度从下往上数，深度从上往下数，因此根节点的深度和叶子节点的高度都是 0；
• 树的层：从根开始定义，根为第一层，根的孩子为第二层；
• N 叉树：由其子节点最多可以有几个决定，最多有 N 个就是 N 叉树。

二叉树：算法题中的绝对主角

二叉树是每个节点最多只有两个子节点的树，习惯上称之为左节点和右节点（注意这只是名字，并不代表实际位置上的左右）。二叉树是算法题最常见的树形态，可以用以下数据结构表示：

Node { value: any; // 当前节点的值 left: Node | null; // 左儿子 right: Node | null; // 右儿子 }

二叉树的常见分类包括：完全二叉树、满二叉树、二叉搜索树、平衡二叉树、红黑树等。二叉树的存储方式有两种：

• 链表存储：每个节点持有左右子节点指针，最常用；
• 数组存储：非常适合完全二叉树，利用节点编号可直接计算父子关系。

树不仅仅是一种数据结构，更是一种思维工具。以最简单的斐波那契数列为例，入参与返回值都不是树，却可以画出递归树来辅助思考：

function fn(n) { if (n == 0 || n == 1) return n; return fn(n - 1) + fn(n - 2); }

递归树中，边表示返回值，节点表示需要计算的值。计算 fn(5) 的过程本质上就是一次树的后序遍历——这直观说明了遍历思维在递归问题中的普适性。本文所讨论的树题，特指输入（参数）或输出（返回值）是树结构的题目。

一个中心：树的遍历

整个树专题只有一个中心点——树的遍历。不管什么题目，核心都是遍历，这是所有树题的地基。

遍历的本质是把树里的每个元素都访问一遍，但访问必须从根节点开始，再根据子节点指针访问子节点。由于子节点有多个方向（二叉树最多两个），就产生了先访问哪个的问题，从而形成了不同的遍历方式。左右子节点的访问顺序通常不重要，极个别情况下（例如要访问树的最左下角节点）顺序才会产生影响。

遍历本身不是目的，遍历是为了更好地处理——包括搜索、修改树等。树虽然只能从根开始访问，但我们可以选择在访问完毕回来之后做处理，还是在访问回来之前做处理，这两种方式分别对应后序遍历和前序遍历。

树的遍历分为两个基本类型：深度优先遍历（DFS）和广度优先遍历（BFS）。这两种遍历并不为树所独有，而是一种逻辑，可以应用于任何数据结构，例如 365. 水壶问题 中就可以对水壶状态（用一个二元组表示）做广度优先遍历。

双色标记法：统一三种遍历的迭代写法

很多人的困惑是：二叉树前中后序的递归写法没问题，但迭代写法写不出来。这里介绍一种统一三种遍历的迭代技巧——双色标记法。它模仿垃圾回收算法中的三色标记法：

• 白色表示尚未访问；
• 灰色表示尚未完全访问子节点；
• 黑色表示子节点全部访问（双色版本中简化为灰、白两色）。

其核心思想：

• 使用颜色标记节点状态，新节点为白色，已访问的节点为灰色；
• 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈；
• 如果遇到的节点为灰色，则将节点的值输出。

使用该方法实现的中序遍历如下：

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: WHITE, GRAY = 0, 1 res = [] stack = [(WHITE, root)] while stack: color, node = stack.pop() if node is None: continue if color == WHITE: stack.append((WHITE, node.right)) stack.append((GRAY, node)) stack.append((WHITE, node.left)) else: res.append(node.val) return res

实现上，WHITE 表示递归中的第一次进入过程，GRAY 表示递归中从叶子节点返回的过程，因此这种迭代写法更接近递归的本质。实现前序、后序遍历只需要调整左右子节点的入栈顺序，其他部分无需任何变化。这个技巧的完整背景可参考仓库中的《二叉树的遍历》专题，其中还介绍了普通迭代、Morris 遍历（可在 O(1) 空间完成遍历）等更多内容。

关于性能的顾虑：双色标记法每个节点入栈出栈两次，比普通迭代多了一倍，但这只是常数项的增加，绝大多数场景影响不大。反过来看，大家日常写的递归由于内存栈开销，性能通常比双色标记法更差。如果彻底掌握了这种写法，再根据递归思想去写一次入栈的迭代也并非难事——无非是调用函数时入栈、函数 return 时出栈。

两个基本点：DFS 与 BFS

树的遍历分为深度优先遍历（DFS）和广度优先遍历（BFS），这就是两个基本点。DFS 细分为前、中、后序遍历，BFS 细分为带层与不带层两种。DFS 适合做暴力枚举类题目，借助函数调用栈可以轻松用递归实现；BFS 适合求最短距离，其核心价值在于可以提前终止。

BFS 不等于层次遍历

**层次遍历和 BFS 是完全不同的东西。**层次遍历就是一层层地按树的层次顺序访问；而 BFS 的核心在于求最短问题时可以提前终止——找到最近目标就直接返回，而 DFS 需要穷举所有可能才能确定最近的目标，这才是 BFS 的核心价值。层次遍历只是"不需要提前终止的 BFS"的副产物。

如果只需要找到任意一个满足条件的节点（不必最近），DFS 和 BFS 没有太大差别，此时为书写简单通常选择 DFS。

深度优先遍历（DFS）

深度优先搜索是一种用于遍历树或图的算法：沿着树的深度遍历节点，尽可能深地搜索树的分支；当节点 v 的所在边都被探寻过，搜索回溯到发现 v 的那条边的起始节点，直到所有节点都被访问为止，属于盲目搜索。深度优先搜索是图论经典算法，其发明者约翰·霍普克洛夫特与罗伯特·塔扬因此获得 1986 年图灵奖。本仓库的 DFS 专题 对 DFS 有更系统的阐述。

算法流程：

1. 首先将根节点放入stack中；
2. 从 stack 中取出第一个节点，检验它是否为目标：找到则结束搜寻并回传结果，否则将它某一个尚未检验过的直接子节点加入 stack；
3. 重复步骤 2；
4. 如果不存在未检测过的直接子节点，将上一级节点加入 stack，重复步骤 2；
5. 重复步骤 4；
6. 若 stack 为空，表示整张图都检查过了，结束搜寻并回传"找不到目标"。

这里的 stack 可以理解为自行实现的栈，也可以理解为调用栈：调用栈即递归，自行实现的栈即迭代。

算法模板：通用的 DFS 模板需要 visited 防止环造成的死循环：

const visited = {} function dfs(i) { if (满足特定条件）{ // 返回结果 or 退出搜索空间 } visited[i] = true // 将当前状态标为已搜索 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } }

而树是不存在环的，因此树的题目大多数不需要 visited，除非对树的结构做了修改（例如把左子树的 left 指针指向自身），或像复制带随机指针的链表那样需要记录已访问节点。因此树的 DFS 更常写作：

function dfs(root) { if (满足特定条件）{ // 返回结果 or 退出搜索空间 } dfs(root.left) dfs(root.right) }

两种常见分类：前序遍历和后序遍历是最常见的两种 DFS 方式，区分标准是主逻辑的位置：

• 主逻辑在左右子树之前执行 → 前序遍历；
• 主逻辑在左右子树之后执行 → 后序遍历；
• 进入和退出时分别执行不同代码 → 混合遍历，但仍以主逻辑位置判定。

中序遍历一般用于二叉搜索树，会在后面的"四个重要概念"部分讲解。

递归遍历的学习技巧：本质是对递归的理解不够。推荐的练习方式是画图 + 手动代入——把递归过程画到纸上，手动代入几次。例如前序遍历下面这棵树：

1 / \ 2 3 / \ 4 5

访问顺序为 1 → 2 → 3 → 4 → 5，多画几次递归展开图，慢慢就对递归有感觉了。

广度优先遍历（BFS）

BFS 采用横向搜索的方式，数据结构上通常采用队列（DFS 借助栈，BFS 借助队列，两者形成鲜明对照）。BFS 比较适合找最短距离/路径和某一个距离的目标，例如力扣 513"在树的最后一行找到最左边的值"，就是求距离根节点最远距离的目标，一个 BFS 模板即可解决。

算法流程：

1. 首先将根节点放入队列中；
2. 从队列中取出第一个节点，并检验它是否为目标：
   • 找到目标，结束搜索并回传结果；
   • 否则将它所有尚未检验过的直接子节点加入队列；
3. 若队列为空，表示整张图都检查过了，回传"找不到目标"；
4. 重复步骤 2。

通用模板：

const visited = {} function bfs() { let q = new Queue() q.push(初始状态) while(q.length) { let i = q.pop() if (visited[i]) continue if (i 是我们要找的目标) return 结果 for (i的可抵达状态j) { if (j 合法) { q.push(j) } } } return 没找到 }

两种常见分类：求最短距离/路径时我们不关心走到第几步，用不标记层的模板；而求"距离某节点距离等于 k 的所有节点"这类问题时，步数信息值得记录，用标记层的模板。

标记层模板（需要返回第 k 层的节点）：

class Solution: def bfs(k): # 使用双端队列，而不是数组。因为数组从头部删除元素的时间复杂度为 N，双端队列的底层实现其实是链表。 queue = collections.deque([root]) # 记录层数 steps = 0 # 需要返回的节点 ans = [] # 队列不空，生命不止！ while queue: size = len(queue) # 遍历当前层的所有节点 for _ in range(size): node = queue.popleft() if (step == k) ans.append(node) if node.right: queue.append(node.right) if node.left: queue.append(node.left) # 遍历完当前层所有的节点后 steps + 1 steps += 1 return ans

不标记层模板：

class Solution: def bfs(k): # 使用双端队列，而不是数组。因为数组从头部删除元素的时间复杂度为 N，双端队列的底层实现其实是链表。 queue = collections.deque([root]) # 队列不空，生命不止！ while queue: node = queue.popleft() # 由于没有记录 steps，因此我们肯定是不需要根据层的信息去判断的。否则就用带层的模板了。 if (node 是我们要找到的) return node if node.right: queue.append(node.right) if node.left: queue.append(node.left) return -1

具体使用哪种，看题目是否需要根据层信息做判断即可。

三种题型

树的题目从大的方向上只有三种：搜索类、构建类和修改类，比例依次降低（搜索类最多，构建类其次，修改类最少）。这一点与链表（修改类居多）形成鲜明对比。

搜索类

搜索类是树题的绝对大头，解法只有 DFS 和 BFS 两种。几乎所有的搜索类题目都可以方便地用递归实现（递归技巧见"七个技巧"中的单/双递归部分）；一小部分用递归不好实现的（如求二叉树任意两点的距离——距离即最短距离）可以用 BFS 借助队列轻松解决。

所有搜索类题目只需把握三个核心点：开始点、结束点和目标。基本套路是：从入口开始 dfs，在 dfs 内部判断是否到达结束点（通常是叶子节点或空节点）；目标是基本值（如数字）就直接返回或用全局变量记录；目标是数组，则通过参数扩展技巧完成。

DFS 搜索套路模板：

# 其中 path 是树的路径， 如果需要就带上，不需要就不带 def dfs(root, path): # 空节点 if not root: return # 叶子节点 if not root.left and not root.right: return path.append(root) # 逻辑可以写这里，此时是前序遍历 dfs(root.left) dfs(root.right) # 需要弹出，不然会错误计算。 # 比如对于如下树： """ 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 """ # 如果不 pop，那么 5 -> 4 -> 11 -> 2 这条路径会变成 5 -> 4 -> 11 -> 7 -> 2，其 7 被错误地添加到了 path path.pop() # 逻辑也可以写这里，此时是后序遍历 return 你想返回的数据

以"剑指 Offer 34. 二叉树中和为某一值的路径"为例：从根节点开始、到叶子节点结束的所有路径搜索出来，挑选出和为目标值的路径，即开始点是根节点、结束点是叶子节点、目标是路径。这类求特定和的题目，可以方便地使用前序遍历 + 参数扩展完成：

class Solution: def pathSum(self, root: TreeNode, target: int) -> List[List[int]]: def backtrack(nodes, path, cur, remain): # 空节点 if not cur: return # 叶子节点 if cur and not cur.left and not cur.right: if remain == cur.val: nodes.append((path + [cur.val]).copy()) return # 选择 path.append(cur.val) # 递归左右子树 backtrack(nodes, path, cur.left, remain - cur.val) backtrack(nodes, path, cur.right, remain - cur.val) # 撤销选择 path.pop(-1) ans = [] # 入口，路径，目标值全部传进去，其中路径和path都是扩展的参数 backtrack(ans, [], root, target) return ans

由于需要找到所有路径而不仅是一条，这里适合回溯暴力枚举（回溯的完整套路见仓库《回溯专题》）。

再以"1372. 二叉树中的最长交错路径"为例：选择任意节点和一个方向（左或右），前进后改变方向，重复直到无法移动，交错路径长度定义为访问节点数减一。这不就是从任意节点开始、到任意节点结束的所有交错路径搜索出来并取最长——开始点与结束点都是任意节点。入口是任意节点的题目，可以方便地使用双递归。交错类题目有一个好用技巧：用 -1 和 1 记录方向，通过乘以 -1 得到另一方向：

next_direction = cur_direction * - 1

886. 可能的二分法 和 785. 判断二分图 都用了这个技巧。

用双递归求解，内部递归需要缓存（如 Python 的 lru_cache），否则容易因重复计算超时：

class Solution: @lru_cache(None) def dfs(self, root, dir): if not root: return 0 if dir == -1: return int(root.left != None) + self.dfs(root.left, dir * -1) return int(root.right != None) + self.dfs(root.right, dir * -1) def longestZigZag(self, root: TreeNode) -> int: if not root: return 0 return max(self.dfs(root, 1), self.dfs(root, -1), self.longestZigZag(root.left), self.longestZigZag(root.right))

构建类

构建类分为普通二叉树的构建和二叉搜索树的构建。

普通二叉树的构建有三种：

1. 给你两种 DFS 遍历的结果数组，构建原始树结构（如根据先序 + 后序遍历数组构造二叉树）。这类题目通常假设输入的遍历序列不含重复数字——因为一旦出现重复值，就无法唯一确定根节点与左右子树的划分。仓库中的构造二叉树系列题解对此讲解得很清楚。
2. 给你一个 BFS 的遍历结果数组，构建原始树结构。最经典的是"剑指 Offer 37. 序列化二叉树"。力扣中所有树的表示都是用数组表示层次遍历结果，部分叶子节点的空子节点也会被打印，例如[1,2,3,null,null,4,5]表示如下二叉树：

1 / \ 2 3 / \ 4 5

如果你彻底理解了 BFS，这种反序列化就难不倒你（完整实现见下文"完全二叉树"小节的代码演进）。 3.给你一种场景描述，构造符合条件的二叉树。例如 654. 最大二叉树，套路与上面类似。

此外还有一种罕见的动态构建，例如 894. 所有可能的满二叉树，直接 BFS 即可。

二叉搜索树的构建：普通二叉树无法根据一种序列重构，因为只知道根节点无法区分左右子树；而二叉搜索树的根节点值大于所有左子树的值、小于所有右子树的值，因此可以根据一种遍历序列构造出来——利用该特性确定左右子树位置后，就转化成了普通二叉树的构建问题，例如 1008. 前序遍历构造二叉搜索树。

修改类

修改类的题目也基于搜索算法（不找到目标怎么删呢？），分两种基本类型。

题目要求的修改：增加、删除节点，或修改节点的值或指向。修改指针的题目一般不难，比如 116. 填充每个节点的下一个右侧节点指针——BFS 时顺便记录上一次访问的同层节点，再增加一个指针即可，套用带层的 BFS 模板即可。增加和删除的题目稍复杂，例如 450. 删除二叉搜索树中的节点、669. 修剪二叉搜索树，可用后序遍历 + 虚拟节点两个套路解决（详见"七个技巧"）。

实际工程中，我们也可以不删除节点，而是给节点做标记表示已删除，这叫做软删除。

算法需要，自己修改：为了方便计算自己加指针。例如 863. 二叉树中所有距离为 K 的结点——通过给节点类增加指向父节点的引用 parent，问题就转化为距离目标节点一定距离的问题，可用带层的 BFS 模板解决。动态语言可以直接加属性，静态语言则需要新增类定义，或用字典实现（key 是节点引用，value 是想记录的东西）：

class Solution { Map<TreeNode, TreeNode> parent; public void dfs(TreeNode node, TreeNode parent) { if (node != null) { parent.put(node, parent); dfs(node.left, node); dfs(node.right, node); } } }

四个重要概念

二叉搜索树（BST）

二叉搜索树亦称二叉查找树，具有下列性质：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的节点。

常规操作有：插入、查找、删除、找父节点、求最大值、求最小值。

天生适合查找：每次向下走都会排除一个分支；如果同时是平衡二叉树，搜索过程时间复杂度为 O(logN)。实际上平衡二叉搜索树的查找与有序数组的二分查找本质相同，只是数据存储方式不同。那为何有了有序数组二分还需要二叉搜索树？因为树结构对动态数据友好——频繁增删时，理论上添加和删除时间复杂度都是 O(h)（h 为树高，平衡时为 O(logN)），而数组的增删是 O(N)。方便搜索是二叉搜索树的设计初衷，不让查找时间复杂度退化到线性是平衡二叉树的初衷。更广义地看，二分的本质是将问题规模缩小一半，与数据结构无关：跳表是链表的二分，二叉搜索树是树的二分。

中序遍历是有序的：二叉搜索树的中序遍历结果是一个有序数组，这个性质对做题帮助极大。例如 98. 验证二叉搜索树 可以直接中序遍历并一边遍历一边判断结果是否单调递增，不是则提前返回 False。再如 99. 恢复二叉搜索树：先中序遍历找出不是递增的节点（被错误交换的节点）然后交换恢复；难点在于错误交换可能发生在中序遍历的相邻节点或非相邻节点，需要分别讨论两种情况。

练习建议：

• 94. 二叉树的中序遍历
• 98. 验证二叉搜索树
• 173. 二叉搜索树迭代器
• 250. 统计同值子树

**碰到二叉搜索树的搜索类题目，一定先想下能不能利用"中序遍历有序"这个性质。**仓库中的《二叉搜索树专题》也值得延伸阅读。

完全二叉树

一棵深度为 k 的有 n 个节点的二叉树，对节点按从上至下、从左到右编号，如果编号为 i（1≤i≤n）的节点与满二叉树中编号为 i 的节点位置相同，则称为完全二叉树。直接考察完全二叉树的题目不多（如 222. 完全二叉树的节点个数，二分可解），但理解它对做题帮助很大。

核心用处：给完全二叉树编号后，父子关系可以通过编号轻松求出。若所有节点从左到右、从上到下从 1 开始编号，已知某节点编号为 i，则：

• 左子节点编号为2 * i；
• 右子节点编号为2 * i + 1；
• 父节点编号为i / 2。

熟悉二叉堆的同学会发现，这就是用数组实现的二叉堆——二叉堆就是完全二叉树的一个应用。

很多题目虽然不是完全二叉树，但我们可以把空节点脑补上去。例如 662. 二叉树最大宽度：

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。 示例 1: 输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

一个带层的 BFS 模板即可搞定，注意两点：入队时除了普通节点还要将空节点入队；出队时除了节点本身还要将节点的位置信息入队（即下方代码的 pos）：

class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: q = collections.deque([(root, 0)]) steps = 0 cur_depth = leftmost = ans = 0 while q: for _ in range(len(q)): node, pos = q.popleft() if node: # 节点编号关系是不是用上了？ q.append((node.left, pos * 2)) q.append((node.right, pos * 2 + 1)) # 逻辑开始 if cur_depth != steps: cur_depth = steps leftmost = pos ans = max(ans, pos - leftmost + 1) # 逻辑结束 steps += 1 return ans

完全二叉树的编号思想还深刻影响了树的序列化。将一颗普通树序列化为数组，只要将空节点当成普通节点入队处理即可：

class Codec: def serialize(self, root): q = collections.deque([root]) ans = '' while q: cur = q.popleft() if cur: ans += str(cur.val) + ',' q.append(cur.left) q.append(cur.right) else: # 除了这里不一样，其他和普通的不记录层的 BFS 没区别 ans += 'null,' # 末尾会多一个逗号，我们去掉它。 return ans[:-1]

细心的读者会发现，上面的序列化并不是真正的完全二叉树序列化（末尾还带着多余的 null），这引出一个经典陷阱。如果反序列化时直接套用完全二叉树的编号关系（i 号节点的左子节点是 2i、右子节点是 2i+1，对应索引 2i-1 与 2i）：

def deserialize(self, data): if data == 'null': return None nodes = data.split(',') root = TreeNode(nodes[0]) # 从一号开始编号，编号信息一起入队 q = collections.deque([(root, 1)]) while q: cur, i = q.popleft() # 2 * i 是左节点，而 2 * i 编号对应的其实是索引为 2 * i - 1 的元素， 右节点同理。 if 2 * i - 1 < len(nodes): lv = nodes[2 * i - 1] if 2 * i < len(nodes): rv = nodes[2 * i] if lv != 'null': l = TreeNode(lv) # 将左节点和 它的编号 2 * i 入队 q.append((l, 2 * i)) cur.left = l if rv != 'null': r = TreeNode(rv) # 将右节点和 它的编号 2 * i + 1 入队 q.append((r, 2 * i + 1)) cur.right = r return root

这段代码在某些 case 下会挂——因为序列化结果并非真正的完全二叉树（中间可能存在空缺）。正确做法是三个指针协同：p1 指向当前处理的节点，p2、p3 指向其左右子节点；p1 每次移动一位，p2、p3 每次移动两位；p1.left = p2; p1.right = p3，直到 p1 移动到最后：

def deserialize(self, data): if data == 'null': return None nodes = data.split(',') root = TreeNode(nodes[0]) q = collections.deque([root]) i = 0 while q and i < len(nodes) - 2: cur = q.popleft() lv = nodes[i + 1] rv = nodes[i + 2] i += 2 if lv != 'null': l = TreeNode(lv) q.append(l) cur.left = l if rv != 'null': r = TreeNode(rv) q.append(r) cur.right = r return root

这道题虽然不是完全二叉树题目，却处处借鉴完全二叉树的编号思想，是理解两者关系的绝佳素材。

路径

树的路径题目变种很多，是经典考点。要理解路径的概念与解法，看 124. 二叉树中的最大路径和 一道题就够。题目定义：路径是一条从树中任意节点出发、沿父节点-子节点连接、达到任意节点的序列，至少包含一个节点，且不一定经过根节点。要点有二：

• 路径可以由一个、两个或多个节点组成，但必须连续；
• 路径必须"直来直去"，不能有分叉（例如某条路径的左下角可以是 3 或 2，但不能同时选）。

看到"从任意节点出发"，大概率要么全局记录最大值，要么双递归。如果使用双递归，复杂度是 O(N²)——而子树的路径和计算出来后可推导父节点的最大路径和，双递归存在重复计算，可用记忆化递归优化。更优的做法是全局记录最大值：递归时只 return 当前的一条边（不能拐弯），并在函数内部计算以当前节点出发的最大路径和，更新全局最大值即可。核心是 return 较大的那条边，因为较小的边不可能是答案：

class Solution: ans = float('-inf') def maxPathSum(self, root: TreeNode) -> int: def dfs(node): if not node: return 0 l = dfs(node.left) r = dfs(node.right) # 选择当前的节点，并选择左右两边，当然左右两边也可以不选。必要时更新全局最大值 self.ans = max(self.ans, max(l,0) + max(r, 0) + node.val) # 只返回一边，因此我们挑大的返回。当然左右两边也可以不选 return max(l, r, 0) + node.val dfs(root) return self.ans

注意这里的 dfs 本质上是后序遍历：需要先拿到左右子树的信息，再结合自身 val 决定如何选取。类似题目如 113. 路径总和 II 也可对照练习。

距离

与路径类似，距离是另一个高频考点，且二者都是搜索类题目的考点——最短路径就是距离，而树的最短路径就是边的数目。练习下面两道题，碰到距离题基本就稳了：

• 834. 树中距离之和
• 863. 二叉树中所有距离为 K 的结点

七个技巧

七个技巧全部基于 DFS（BFS 掌握了模板即可，基本没有技巧可言）。前面的内容多为战略思想，这一节才是可落地的实操干货。

技巧一：dfs(root)

写树的 DFS 时，将函数中表示当前节点的形参也写成 root，而不是 node。原因有二：

1. 形参写 node 时经常误写成 root 导致出错（不会抛错，不易发现），统一写 root 就不会有这个问题；
2. 相当于把 root 当成 current 指针使用：最开始 current 指向 root，之后不断修改指向树的其它节点，概念上只有一个当前指针，而用 node 则是当前指针 + root 指针两个概念。

技巧二：单/双递归

递归让代码简洁、不易出错。树的题目大多数可以用递归轻松解决——如果一个递归不行，那么来两个（至今没见过三递归或更多）。什么时候需要双递归？题目有类似"任意节点开始 xxxx"或"所有 xxx"的说法时，就可以考虑双递归。但如果递归中有重复计算，则使用双递归 + 记忆化或直接单递归。例如"面试题 04.12. 求和路径"和 563. 二叉树的坡度，都可以考虑双递归求解。

双递归的基本套路：一个主递归函数负责计算以某一个节点开始的 xxxx，一个内部递归函数负责计算xxxx，从而实现对所有节点的枚举：

def dfs_inner(root): # 这里写你的逻辑，就是前序遍历 dfs_inner(root.left) dfs_inner(root.right) # 或者在这里写你的逻辑，那就是后序遍历 def dfs_main(root): return dfs_inner(root) + dfs_main(root.left) + dfs_main(root.right)

技巧三：前后遍历

链表只有一个 next 指针，只有两种遍历；二叉树有两个指针，常见遍历有三个，除前后序外还有中序（中序除了二叉搜索树，其他地方用得不多）。掌握树的前后序只需记住一句话：如果是前序遍历，你可以想象上面的节点都处理好了，怎么处理的不用管；如果是后序遍历，你可以想象下面的树都处理好了，怎么处理的不用管。

更形象地说是自顶向下与自底向上：

• 自顶向下：在每个递归层级首先访问节点计算一些值，并在递归调用时将这些值通过参数传到子树中；
• 自底向上：首先对所有子节点递归调用函数，然后根据返回值和根节点本身的值得到答案。

经验总结：

• 大多数树的题使用后序遍历比较简单，且大多依赖左右子树的返回值，例如 1448. 统计二叉树中好节点的数目；
• 不多的问题需要前序遍历，前序遍历通常结合参数扩展技巧，例如 1022. 从根到叶的二进制数之和；
• 如果你能用参数和节点本身的值决定传给子节点的参数，就用前序遍历；
• 如果知道子节点的答案就能计算出当前节点的答案，就用后序遍历；
• 遇到二叉搜索树则考虑中序遍历。

技巧四：虚拟节点

不仅链表有虚拟节点技巧，树也有，这一点容易忽视。什么时候使用：

• 树的头（根）节点会被修改：新建虚拟节点当新根，就不用考虑第一个节点被删的问题（虚拟节点不参与题目运算）；
• 题目需要返回树中间的某个节点（而非根节点）：可新建虚拟头，让虚拟头在恰当时候（刚好指向需要返回的节点）断开连接，返回虚拟头的 next 即可。

以 814. 二叉树剪枝为例（移除所有不包含 1 的子树，根节点可能被整个移除）：

var pruneTree = function (root) { function dfs(root) { if (!root) return 0; const l = dfs(root.left); const r = dfs(root.right); if (l == 0) root.left = null; if (r == 0) root.right = null; return root.val + l + r; } ans = new TreeNode(-1); ans.left = root; dfs(ans); return ans.left; };

计算子树和只需后序遍历一次并收集值，配合虚拟节点即可完美处理根节点被删除的边界。

再以 1325. 删除给定值的叶子节点为例：题目要求重复删除值为 target 的叶子节点，直到不能继续删除。这是一个自底向上的过程，因此用后序遍历；树的删除需要父节点，与链表删除类似，记录当前节点的父节点，并通过参数扩展向下传递。二叉树有两个指针 left 和 right，因此还要记录当前节点是其父节点的哪个孩子：

class Solution: def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode: def dfs(node, parent, is_left=True): if not node: return dfs(node.left, node, True) dfs(node.right, node, False) if node.val == target and parent and not node.left and not node.right: if is_left: parent.left = None else: parent.right = None ans = TreeNode(-1) ans.left = root dfs(root, ans) return ans.left

技巧五：边界

边界考虑不全是人类的本能，只能靠多练克服。树有三种题型，边界侧重点各不相同。

搜索类的边界最简单，90% 以上的题目只有两种情况：

def dfs(root): if not root: print('是空节点，你需要返回合适的值') if not root.left and not root.right: print('是叶子节点，你需要返回合适的值') # your code here

经过这样的处理，后面的代码基本都不需要判空了。

构建类的边界更麻烦，常见两个：

1. 参数扩展的边界。例如 1008 根据前序遍历构造二叉搜索树时容易漏掉 start == end 的情况：

def bstFromPreorder(self, preorder: List[int]) -> TreeNode: def dfs(start, end): if start > end: return None if start == end: return TreeNode(preorder[start]) root = TreeNode(preorder[start]) mid = -1 for i in range(start + 1, end + 1): if preorder[i] > preorder[start]: mid = i break if mid == -1: root.left = dfs(start + 1, end) else: root.left = dfs(start + 1, mid - 1) root.right = dfs(mid, end) return root return dfs(0, len(preorder) - 1)

注意补上if start == end: return TreeNode(preorder[start])这个边界判断。

2. 虚拟节点：搜索类的虚拟节点技巧同样适用于构建类。

技巧六：参数扩展大法

最简单的 dfs 形如def dfs(root): ...，而很多时候我们需要 dfs 携带更多信息。典型有三种情况：

1. 携带父亲或爷爷的信息：

def dfs(root, parent): if not root: return dfs(root.left, root) dfs(root.right, root)

2. 携带路径信息（路径和或具体路径数组）。路径和：

def dfs(root, path_sum): if not root: # 这里可以拿到根到叶子的路径和 return path_sum dfs(root.left, path_sum + root.val) dfs(root.right, path_sum + root.val)

路径（注意回溯撤销）：

def dfs(root, path): if not root: # 这里可以拿到根到叶子的路径 return path path.append(root.val) dfs(root.left, path) dfs(root.right, path) # 撤销 path.pop()

可以用"面试题 04.12. 求和路径"练手。需要传递额外信息给子节点（关键字是子节点）时，务必掌握这种技巧——这也解释了为什么参数扩展经常用于前序遍历。

3. 二叉搜索树的搜索题大多需要扩展参数，且扩展方式固定：将最大值和最小值通过参数传递到左右子树，类似dfs(root, lower, upper)，递归过程中更新最大最小值即可。注意(lower, upper)是一个左右都开放的区间。例如 783. 二叉搜索树节点最小距离，除中序遍历法外，也可用左右边界法：

class Solution: def minDiffInBST(self, root): def dfs(node, lower, upper): if not node: return upper - lower left = dfs(node.left, lower, node.val) right = dfs(node.right, node.val, upper) # 要么在左，要么在右，不可能横跨（因为是 BST） return min(left, right) return dfs(root, float('-inf'), float('inf'))

该技巧不只适用于二叉搜索树。例如 1026. 节点与其祖先之间的最大差值，同样套路轻松求解：

class Solution: def maxAncestorDiff(self, root: TreeNode) -> int: def dfs(root, lower, upper): if not root: return upper - lower # 要么在左，要么在右，要么横跨。 return max(dfs(root.left, min(root.val, lower), max(root.val, upper)), dfs(root.right, min(root.val, lower), max(root.val, upper))) return dfs(root, float('inf'), float('-inf'))

技巧七：返回元组/列表

通常 dfs 的返回值是单值，而有时候为了方便计算会返回数组或元组（个数固定用元组）。这个技巧与参数扩展有异曲同工之妙，只是一个作用于函数参数，一个作用于函数返回值。

返回元组：以 865. 具有所有最深节点的最小子树为例，一个简单想法是 dfs 返回深度，通过比较左右子树深度定位答案：

class Solution: def subtreeWithAllDeepest(self, root: TreeNode) -> int: def dfs(node, d): if not node: return d l_d = dfs(node.left, d + 1) r_d = dfs(node.right, d + 1) if l_d >= r_d: return l_d return r_d return dfs(root, -1)

但题目要求返回节点引用，因此要除了返回深度，也要把节点返回：

class Solution: def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode: def dfs(node, d): if not node: return (node, d) l, l_d = dfs(node.left, d + 1) r, r_d = dfs(node.right, d + 1) if l_d == r_d: return (node, l_d) if l_d > r_d: return (l, l_d) return (r, r_d) return dfs(root, -1)[0]

返回数组：dfs 返回数组比较少见，主要用于计算笛卡尔积——需要用到笛卡尔积时，考虑返回数组的方式。一个不太准确的提示：题目出现"所有可能""所有情况"字样时，可考虑此技巧。典型题目是 1530. 好叶子节点对的数量。

两个叶子节点的最短路径（距离）可以用最近公共祖先辅助计算：两叶子节点最短路径 = 其中一个叶子到最近公共祖先的距离 + 另一个叶子到最近公共祖先的距离。定义 dfs(root) 计算以 root 为出发点到其各个叶子节点的距离（返回距离数组）；父节点只需把子树的每一项加 1（父到各叶子距离 = 1 + 子节点到各叶子距离）。因为需要先计算子树信息，所以选择后序遍历：

class Solution: def countPairs(self, root: TreeNode, distance: int) -> int: self.ans = 0 def dfs(root): if not root: return [] if not root.left and not root.right: return [0] ls = [l + 1 for l in dfs(root.left)] rs = [r + 1 for r in dfs(root.right)] # 笛卡尔积 for l in ls: for r in rs: if l + r <= distance: self.ans += 1 return ls + rs dfs(root) return self.ans

894. 所有可能的满二叉树也是同样的套路，可用上面的知识练习。

经典题目

推荐先把本文提到的题目都做一遍，然后用所学知识做下面十道练习题检验成果：

• 剑指 Offer 55 - I. 二叉树的深度
• 剑指 Offer 34. 二叉树中和为某一值的路径
• 101. 对称二叉树
• 226. 翻转二叉树
• 543. 二叉树的直径
• 662. 二叉树最大宽度
• 971. 翻转二叉树以匹配先序遍历
• 987. 二叉树的垂序遍历
• 863. 二叉树中所有距离为 K 的结点
• 面试题 04.06. 后继者

总结

树的题目有一个中心点——遍历，这是搜索问题和修改问题的基础。遍历从大的方向分为广度优先遍历和深度优先遍历，这就是两个基本点：BFS 有带层信息与不带层信息两种（会带层的就够了），DFS 常见的是前序与后序，中序多用于二叉搜索树（其中序遍历是严格递增的数组）。

树的题目从大的方向看就三种：搜索类最多，牢牢把握开始点、结束点和目标即可；构建类一句话概括——根据一种遍历结果确定根节点位置，根据另一种遍历结果（二叉搜索树则不需要）确定左右子树；修改类不多，但边界需要特殊考虑（这是与搜索问题的本质区别），可用虚拟节点技巧，搜索问题返回值不是根节点时也可考虑虚拟节点。

树有四个对做题帮助很大的概念：完全二叉树、二叉搜索树、路径和距离，相关题目都很经典，推荐认真做一遍。最后，七个实操技巧（dfs(root) 命名、单/双递归、前后遍历、虚拟节点、边界、参数扩展、返回元组/列表）都明确了适用场景，找几个题目试试便知。仓库中的《二叉树的遍历》专题、《DFS 专题》、《回溯专题》 与本文互为补充，可对照阅读，形成完整的树专题知识体系。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode