关于算法:几乎刷完了力扣所有的树题我发现了这些东西

先高低本文的提纲，这个是我用 mindmap 画的一个脑图，之后我会持续欠缺，将其余专题逐步完善起来。

大家也能够应用 vscode blink-mind 关上源文件查看，外面有一些笔记能够点开查看。源文件能够去我的公众号《力扣加加》回复脑图获取，当前脑图也会继续更新更多内容。vscode 插件地址：https://marketplace.visualstu…

本系列蕴含以下专题：

简直刷完了力扣所有的链表题，我发现了这些货色。。。
简直刷完了力扣所有的树题，我发现了这些货色。。。(就是本文)

<!– more –>

首先亮一下本文的配角 – 树（我的化妆技术还行吧 ^\_^）：

树标签在 leetcode 一共有 175 道题。为了筹备这个专题，我花了几天工夫将 leetcode 简直所有的树题目都刷了一遍。

除了 35 个上锁的，1 个不能做的题（1628 题不晓得为啥做不了），4 个标着树的标签但却是图的题目，其余我都刷了一遍。通过集中刷这些题，我发现了一些乏味的信息，明天就分享给大家。

大家好，我是 lucifer。明天给大家带来的是《树》专题。另外为了放弃章节的聚焦性和实用性，省去了一些内容，比方哈夫曼树，前缀树，均衡二叉树（红黑树等），二叉堆。这些内容相对来说实用性没有那么强，如果大家对这些内容也感兴趣，能够关注下我的仓库 leetcode 算法题解，大家有想看的内容也能够留言通知我哦~

另外要提前告知大家的是本文所讲的很多内容都很依赖于递归。对于递归的练习我举荐大家把递归过程画到纸上，手动代入几次。等大脑相熟了递归之后就不必这么辛苦了。切实懒得画图的同学也能够找一个可视化递归的网站，比方 https://recursion.now.sh/。等你对递归有了肯定的了解之后就认真钻研一下树的各种遍历办法，再把本文看完，最初把文章开端的题目做一做，搞定个递归问题不大。

文章的前面《两个基本点 – 深度优先遍历》局部，对于如何练习树的遍历的递归思维我也提出了一种办法

最初要强调的是，本文只是帮忙你搞定树题目的常见套路，但不是说树的所有题目波及的考点都讲。比方树状 DP 这种不在本文的探讨范畴，因为这种题更偏重的是 DP，如果你不懂 DP 多半是做不进去的，你须要的是学完树和 DP 之后再去学树状 DP。如果你对这些内容感兴趣，能够期待我的后续专题。

提到树大家更相熟的是事实中的树，而事实中的树是这样的：

而计算机中的树其实是事实中的树的倒影。

计算机的数据结构是对事实世界物体间关系的一种形象。比方家族的族谱，公司架构中的人员组织关系，电脑中的文件夹构造，html 渲染的 dom 构造等等，这些有档次关系的构造在计算机领域都叫做树。

首先明确一下，树其实是一种逻辑构造。比方笔者平时写简单递归的时候，只管笔者做的题目不是树，也会画一个递归树帮忙本人了解。

树是一种重要的思维工具

以最简略的计算 fibonacci 数列为例：

function fn(n) {if (n == 0 || n == 1) return n;

  return fn(n - 1) + fn(n - 2);
}

很显著它的入参和返回值都不是树，然而却不影响咱们用树的思维去思考。

持续回到下面的代码，依据下面的代码能够画出如下的递归树。

其中树的边示意的是返回值，树节点示意的是须要计算的值，即 fn(n）。

以计算 5 的 fibbonacci 为例，过程大略是这样的（动图演示）：

这其实就是一个树的后序遍历，你说树（逻辑上的树）是不是很重要？对于后序遍历咱们前面再讲，当初大家晓得是这么回事就行。

大家也能够去这个网站查看下面算法的单步执行成果。当然这个网站还有更多的算法的动画演示。

下面的图箭头方向是为了不便大家了解。其实箭头方向变成向下的才是真的树结构。

狭义的树真的很有用，然而它范畴太大了。本文所讲的树的题目是比拟狭窄的树，指的是输出（参数）或者输入（返回值）是树结构的题目。

<!– more –>

树的基本概念难度都不大，为了节俭篇幅，我这里简略过一下。对于你不相熟的点，大家自行去查找一下相干材料。我置信大家也不是来看这些的，大家应该想看一些不一样的货色，比如说一些做题的套路。

树是一种非线性数据结构。树结构的根本单位是节点。节点之间的链接，称为分支（branch）。节点与分支造成树状，构造的开始，称为根（root），或根结点。根节点之外的节点，称为子节点（child）。没有链接到其余子节点的节点，称为叶节点（leaf）。如下图是一个典型的树结构：

每个节点能够用以下数据结构来示意：

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

其余重要概念：

树的高度：节点到叶子节点的最大值就是其高度。
树的深度：高度和深度是相同的，高度是从下往上数，深度是从上往下。因而根节点的深度和叶子节点的高度是 0。
树的层：根开始定义，根为第一层，根的孩子为第二层。
二叉树，三叉树，。。。N 叉树，由其子节点最多能够有几个决定，最多有 N 个就是 N 叉树。

二叉树是树结构的一种，两个叉就是说每个节点最多只有两个子节点，咱们习惯称之为左节点和右节点。

留神这个只是名字而已，并不是理论地位上的左右

二叉树也是咱们做算法题最常见的一种树，因而咱们花大篇幅介绍它，大家也要花大量工夫重点把握。

二叉树能够用以下数据结构示意：

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

齐全二叉树
满二叉树
二叉搜寻树
均衡二叉树
红黑树
。。。

链表存储
数组存储。非常适合齐全二叉树

很多人感觉树是一个很难的专题。实际上，只有你把握了窍门，它并没那么难。

从官网的难度标签来看，树的题目处于艰难难度的一共是 14 道，这其中还有 1 个标着树的标签然而却是图的题目，因而艰难率是 13 / 175，也就是 7.4 % 左右。如果排除上锁的 5 道，艰难的只有 9 道。大多数艰难题，置信你看完本节的内容，也能够做进去。

从通过率来看，只有 不到三分之一 的题目均匀通过率在 50% 以下，其余（绝大多数的题目）通过率都是 50% 以上。50% 是一个什么概念呢？这其实很高了。举个例子来说，BFS 的均匀通过率差不多在 50%。而大家认为比拟难的二分法和动静布局的均匀通过率差不多 40%。

大家不要对树有压力，树和链表一样是绝对容易的专题，明天 lucifer 给大家带来了一个口诀 一个核心，两个基本点，三种题型，四个重要概念，七个技巧，帮忙你克服树这个难关。

一个核心指的是 树的遍历。整个树的专题只有一个中心点，那就是树的遍历，大家务必牢牢记住。

不论是什么题目，外围就是树的遍历，这是所有的根底，不会树的遍历前面讲的都是白搭。

其实树的遍历的实质就是去把树里边儿的每个元素都拜访一遍（任何数据结构的遍历不都是如此么？）。但怎么拜访的？我不能间接拜访叶子节点啊，我必须得从根节点开始拜访，而后依据子节点指针拜访子节点，然而子节点有多个（二叉树最多两个）方向，所以又有了先拜访哪个的问题，这造成了不同的遍历形式。

左右子节点的拜访程序通常不重要，极个别状况下会有一些奥妙区别。比如说咱们想要拜访一棵树的最左下角节点，那么程序就会产生影响，但这种题目会比拟少一点。

而遍历不是目标，遍历是为了更好地做解决，这里的解决包含搜寻，批改树等。树尽管只能从根开始拜访，然而咱们能够抉择在拜访结束回来的时候做解决，还是在拜访回来之前做解决，这两种不同的形式就是 后序遍历 和先序遍历。

对于具体的遍历，前面会给大家具体讲，当初只有晓得这些遍历是怎么来的就行了。

而树的遍历又能够分为两个根本类型，别离是深度优先遍历和广度优先遍历。这两种遍历形式并不是树特有的，但却随同树的所有题目。值得注意的是，这两种遍历形式只是一种逻辑而已，因而实践能够利用于任何数据结构，比方 365. 水壶问题中，就能够对水壶的状态应用广度优先遍历，而水壶的状态能够用 一个二元组 来示意。

遗憾的是这道题的广度优先遍历解法在 LeetCode 上提交会超时

很多小朋友示意二叉树前中后序的递归写法没问题，然而迭代就写不进去，问我有什么好的办法没有。

这里就给大家介绍一种写迭代遍历树的实操技巧，对立三种树的遍历形式，包你不会错，这个办法叫做双色标记法。如果你会了这个技巧，那么你平时练习大可 只用递归。而后面试的时候，真的要求用迭代或者是对性能有特地要求的那种题目，那你就用我的办法套就行了，上面我来具体讲一下这种办法。

咱们晓得垃圾回收算法中，有一种算法叫三色标记法。即：

用红色示意尚未拜访
灰色示意尚未齐全拜访子节点
彩色示意子节点全副拜访

那么咱们能够模拟其思维，应用双色标记法来对立三种遍历。

其核心思想如下：

应用色彩标记节点的状态，新节点为红色，已拜访的节点为灰色。
如果遇到的节点为红色，则将其标记为灰色，而后将其右子节点、本身、左子节点顺次入栈。
如果遇到的节点为灰色，则将节点的值输入。

应用这种办法实现的中序遍历如下：

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 遍历呢？

morris 遍历是能够在常数的空间复杂度实现树的遍历的一种算法。

我认为在大多数状况下，大家对这种细小的差别能够不必太关注。另外如果这种遍历形式齐全把握了，再依据递归的思维去写一次入栈的迭代也不是难事。无非就是调用函数的时候入栈，函数 return 时候出栈罢了。更多二叉树遍历的内容，大家也能够拜访我之前写的专题《二叉树的遍历》。

简略总结一下，树的题目一个核心就是树的遍历。树的遍历分为两种，别离是深度优先遍历和广度优先遍历。对于树的不同深度优先遍历（前序，中序和后序遍历）的迭代写法是大多数人容易犯错的中央，因而我介绍了一种对立三种遍历的办法 – 二色标记法，这样大家当前写迭代的树的前中后序遍历就再也不必怕了。如果大家彻底相熟了这种写法，再去记忆和练习一次入栈甚至是 Morris 遍历即可。

其实用一次入栈和出栈的迭代实现递归也很简略，无非就是还是用递归思维，只不过你把递归体放到循环里边而已。大家能够在相熟递归之后再回头看看就容易了解了。树的深度遍历的递归技巧，咱们会在前面的《两个基本点》局部解说。

下面提到了树的遍历有两种根本形式，别离是 深度优先遍历（以下简称 DFS）和广度优先遍历（以下简称 BFS），这就是两个基本点。这两种遍历形式上面又会细分几种形式。比方 DFS 细分为前中后序遍历，BFS 细分为带层的和不带层的。

DFS 适宜做一些暴力枚举的题目，DFS 如果借助函数调用栈，则能够轻松地应用递归来实现。

而 BFS 适宜求最短距离，这个和档次遍历是不一样的，很多人搞混。这里强调一下，档次遍历和 BFS 是 齐全不一样 的货色。

档次遍历就是一层层遍历树，依照树的档次程序进行拜访。

（档次遍历图示）

BFS 的外围在于求最短问题时候能够提前终止，这才是它的外围价值，档次遍历是一种不须要提前终止的 BFS 的副产物。这个提前终止不同于 DFS 的剪枝的提前终止，而是找到最近指标的提前终止。比方我要找间隔最近的指标节点，BFS 找到指标节点就能够间接返回。而 DFS 要穷举所有可能能力找到最近的，这才是 BFS 的外围价值。实际上，咱们也能够应用 DFS 实现档次遍历的成果，借助于递归，代码甚至会更简略。

如果找到任意一个满足条件的节点就好了，不用最近的，那么 DFS 和 BFS 没有太大差异。同时为了书写简略，我通常会抉择 DFS。

以上就是两种遍历形式的简略介绍，上面咱们对两者进行一个具体的解说。

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜寻树的分支。当节点 v 的所在边都己被探寻过，搜寻将回溯到发现节点 v 的那条边的起始节点。这一过程始终进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则抉择其中一个作为源节点并反复以上过程，整个过程重复进行直到所有节点都被拜访为止，属于 自觉搜寻。

深度优先搜寻是图论中的经典算法，利用深度优先搜索算法能够产生指标图的相应拓扑排序表，利用拓扑排序表能够不便的解决很多相干的图论问题，如最大门路问题等等。因创造「深度优先搜索算法」，约翰 · 霍普克洛夫特与罗伯特 · 塔扬在 1986 年独特取得计算机领域的最高奖：图灵奖。

截止目前（2020-02-21），深度优先遍历在 LeetCode 中的题目是 129 道。在 LeetCode 中的题型相对是超级小户了。而对于树的题目，咱们基本上都能够应用 DFS 来解决，甚至咱们能够基于 DFS 来做档次遍历，而且因为 DFS 能够基于递归去做，因而算法会更简洁。在对性能有很高要求的场合，我倡议你应用迭代，否则尽量应用递归，不仅写起来简略疾速，还不容易出错。

DFS 图解：

(图片来自 https://github.com/trekhleb/j…

首先将根节点放入 stack 中。
从 stack 中取出第一个节点，并测验它是否为指标。如果找到所有的节点，则完结搜查并回传后果。否则将它某一个尚未测验过的间接子节点退出 stack 中。
反复步骤 2。
如果不存在未检测过的间接子节点。将上一级节点退出 stack 中。
反复步骤 2。
反复步骤 4。
若 stack 为空，示意整张图都查看过了——亦即图中没有欲搜查的指标。完结搜查并回传“找不到指标”。

这里的 stack 能够了解为本人实现的栈，也能够了解为调用栈。如果是调用栈的时候就是递归，如果是本人实现的栈的话就是迭代。

一个典型的通用的 DFS 模板可能是这样的：

const visited = {}
function dfs(i) {
    if (满足特定条件）{// 返回后果 or 退出搜寻空间}

    visited[i] = true // 将以后状态标为已搜寻
    for (依据 i 能达到的下个状态 j) {if (!visited[j]) { // 如果状态 j 没有被搜寻过
            dfs(j)
        }
    }
}

下面的 visited 是为了避免因为环的存在造成的死循环的。而咱们晓得树是不存在环的，因而树的题目大多数不须要 visited，除非你对树的构造做了批改，比方就左子树的 left 指针指向本身，此时会有环。再比方 138. 复制带随机指针的链表这道题须要记录曾经复制的节点，这些须要记录 visited 信息的树的题目 少之又少。

因而一个树的 DFS 更多是：


function dfs(root) {
    if (满足特定条件）{// 返回后果 or 退出搜寻空间}
    for (const child of root.children) {dfs(child)
    }
}

而简直所有的题目简直都是二叉树，因而上面这个模板更常见。

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

而咱们不同的题目除了 if (满足特定条件局部不同之外)，还会写一些特有的逻辑，这些逻辑写的地位不同，成果也截然不同。那么地位不同会有什么影响，什么时候应该写哪里呢？接下来，咱们就聊聊两种常见的 DFS 形式。

前序遍历和后序遍历是最常见的两种 DFS 形式。而另外一种遍历形式（中序遍历）个别用于均衡二叉树，这个咱们前面的 四个重要概念 局部再讲。

前序遍历

如果你的代码大略是这么写的（留神次要逻辑的地位）：

function dfs(root) {
    if (满足特定条件）{// 返回后果 or 退出搜寻空间}
    // 次要逻辑
    dfs(root.left)
    dfs(root.right)
}

那么此时咱们称为前序遍历。

后续遍历

而如果你的代码大略是这么写的（留神次要逻辑的地位）：

function dfs(root) {
    if (满足特定条件）{// 返回后果 or 退出搜寻空间}
    dfs(root.left)
    dfs(root.right)
    // 次要逻辑
}

那么此时咱们称为后序遍历。

值得注意的是，咱们有时也会会写出这样的代码：

function dfs(root) {
    if (满足特定条件）{// 返回后果 or 退出搜寻空间}
    // 做一些事
    dfs(root.left)
    dfs(root.right)
    // 做另外的事
}

如上代码，咱们在进入和退出左右子树的时候别离执行了一些代码。那么这个时候，是前序遍历还是后续遍历呢？实际上，这属于混合遍历了。不过咱们这里只思考 主逻辑 的地位，关键词是 主逻辑。

如果代码主逻辑在左右子树之前执行，那么就是前序遍历。如果代码主逻辑在左右子树之后执行，那么就是后序遍历。对于更具体的内容，我会在 七个技巧 中的 前后遍历 局部解说，大家先留个印象，晓得有着两种形式就好。

递归遍历的学习技巧

下面的《一个核心》局部，给大家介绍了一种干货技巧《双色遍历》对立三种遍历的迭代写法。而树的遍历的递归的写法其实大多数人都没问题。为什么递归写的没问题，用栈写迭代就有问题呢? 实质上其实还是对递归的了解不够。那 lucifer 明天给大家介绍一种练习递归的技巧。其实文章结尾也提到了，那就是画图 + 手动代入。有的同学不晓得怎么画，这里我抛砖引玉分享一下我学习递归的画法。

比方咱们要前序遍历一棵这样的树：

图画的还算比较清楚，就不多解释了。大家遇到题目多画几次这样的递归图，缓缓就对递归有感觉了。

树的遍历的两种形式别离是 DFS 和 BFS，方才的 DFS 咱们简略过了一下前序和后序遍历，对它们有了一个简略印象。这一大节，咱们来看下树的另外一种遍历形式 – BFS。

BFS 也是图论中算法的一种，不同于 DFS，BFS 采纳横向搜寻的形式，在数据结构上通常采纳队列构造。留神，DFS 咱们借助的是栈来实现，而这里借助的是队列。

BFS 比拟适宜找 最短距离 / 门路 和某一个间隔的指标 。比方 给定一个二叉树，在树的最初一行找到最右边的值。，此题是力扣 513 的原题。这不就是求间隔根节点 最远距离 的指标么？一个 BFS 模板就解决了。

BFS 图解：

(图片来自 https://github.com/trekhleb/j…

首先将根节点放入队列中。
从队列中取出第一个节点，并测验它是否为指标。
- 如果找到指标，则完结搜寻并回传后果。
- 否则将它所有尚未测验过的间接子节点退出队列中。
若队列为空，示意整张图都查看过了——亦即图中没有欲搜寻的指标。完结搜寻并回传“找不到指标”。
反复步骤 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 没找到
}

BFS 我目前应用的模板就两种，这两个模板能够解决所有的树的 BFS 问题。

后面我提到了“BFS 比拟适宜找 最短距离 / 门路 和某一个间隔的指标”。如果我需要求的是最短距离 / 门路，我是不关怀我走到第几步的，这个时候可是用不标记层的指标。而如果我需要求间隔某个节点间隔等于 k 的所有节点，这个时候第几步这个信息就值得被记录了。

小于 k 或者大于 k 也是同理。

标记层

一个常见的 BFS 模板，代入题目只须要依据题目微调即可。

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

不标记层

不带层的模板更简略，因而大家其实只须要把握带层信息的指标就够了。

一个常见的 BFS 模板，代入题目只须要依据题目微调即可。

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

以上就是 BFS 的两种根本形式，即带层和不带层，具体应用哪种看题目是否须要依据层信息做判断即可。

树的遍历是前面所有内容的根底，而树的遍历的两种形式 DFS 和 BFS 到这里就简略告一段落，当初大家只有晓得 DFS 和 BFS 别离有两种常见的形式就够了，前面我会给大家具体补充。

树的题目就三种类型，别离是：搜寻类，构建类和批改类，而这三类题型的比例也是逐步升高的，即搜寻类的题目最多，其次是构建类，最初是批改类。这一点和链表有很大的不同，链表更多的是批改类。

接下来，lucifer 给大家逐个解说这三种题型。

搜寻类的题目是树的题目的相对大头。而搜寻类只有两种解法，那就是 DFS 和 BFS，上面别离介绍。

简直所有的搜寻类题目都能够不便地应用递归来实现，对于递归的技巧会在 七个技巧中的单 / 双递归 局部解说。还有一小部分应用递归不好实现，咱们能够应用 BFS，借助队列轻松实现，比方最经典的是求二叉树任意两点的间隔，树的间隔其实就是最短距离，因而能够用 BFS 模板解决。这也是为啥我说 DFS 和 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:
                    res.append((path + [cur.val]).copy())
                return
            # 抉择
            tepathmp.append(cur.val)
            # 递归左右子树
            backtrack(nodes, path, cur.left, remain - cur.val)
            backtrack(nodes, path, cur.right, remain - cur.val)
            # 撤销抉择
            path.pop(-1)
        ans = []
        # 入口，门路，目标值全副传进去，其中门路和 path 都是扩大的参数
        dfs(ans, [], root, target, )
        return ans

再比方：1372. 二叉树中的最长交织门路，题目形容：

给你一棵以 root 为根的二叉树，二叉树中的交织门路定义如下：抉择二叉树中 任意 节点和一个方向（左或者右）。如果前进方向为右，那么挪动到以后节点的的右子节点，否则挪动到它的左子节点。扭转前进方向：左变右或者右变左。反复第二步和第三步，直到你在树中无奈继续移动。交织门路的长度定义为：拜访过的节点数目 - 1（单个节点的门路长度为 0）。请你返回给定树中最长 交织门路 的长度。比方：

此时须要返回 3
解释：蓝色节点为树中最长交织门路（右 -> 左 -> 右）。

这不就是从任意节点开始，到任意节点完结的所有交织门路全副 搜寻进去，挑选出最长的么？这里的开始点是树中的任意节点，完结点也是任意节点，指标就是最长的交织门路。

对于入口是任意节点的题目，咱们都能够不便地应用 双递归 来实现，对于这个，我会在 七个技巧中的单 / 双递归局部 开展。

对于这种交织类的题目，一个好用的技巧是应用 -1 和 1 来记录方向，这样咱们就能够通过乘以 -1 失去另外一个方向。

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

用代码示意就是：

next_direction = cur_direction * - 1

这里咱们应用双递归即可解决。如果题目限定了只从根节点开始，那就能够用单递归解决了。值得注意的是，这里外部递归须要 cache 一下，不然容易因为反复计算导致超时。

我的代码是 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))

这个代码不懂没关系，大家只有晓得搜寻类题目的大方向即可，具体做法咱们前面会介绍，大家留个印象就行。更多的题目以及这些技巧的具体应用形式放在 七个技巧局部 开展。

这种类型相比 DFS，题目数量明显降低，套路也少很多。题目大多是求间隔，套用我下面的两种 BFS 模板根本都能够轻松解决，这个不多介绍了。

除了搜寻类，另外一个大头是构建类。构建类又分为两种：一般二叉树的构建和二叉搜寻树的构建。

而一般二叉树的构建又分为三种：

给你两种 DFS 的遍历的后果数组，让你构建出原始的树结构。比方依据先序遍历和后序遍历的数组，结构原始二叉树。这种题我在结构二叉树系列系列里讲的很分明了，大家能够去看看。

这种题目假如输出的遍历的序列中都不含反复的数字，想想这是为什么。

给你一个 BFS 的遍历的后果数组，让你构建出原始的树结构。

最经典的就是剑指 Offer 37. 序列化二叉树。咱们晓得力扣的所有的树示意都是应用数字来示意的，而这个数组就是一棵树的档次遍历后果，局部叶子节点的子节点（空节点）也会被打印。比方：[1,2,3,null,null,4,5]，就示意的是如下的一颗二叉树：

咱们是如何依据这样的一个档次遍历后果结构出原始二叉树的呢？这其实就属于结构二叉树的内容，这个类型目前力扣就这一道题。这道题如果你彻底了解 BFS，那么就难不倒你。

还有一种是给你形容一种场景，让你结构一个符合条件的二叉树。这种题和下面的没啥区别，套路几乎不要太像，比方 654. 最大二叉树，我就不多说了，大家通过这道题练习一下就晓得了。

除了这种动态构建，还有一种很很常见的动静构建二叉树的，比方 894. 所有可能的满二叉树 , 对于这个题，间接 BFS 就好了。因为这种题很少，因而不做多的介绍。大家只有把最外围的把握了，这种货色天然瓜熟蒂落。

一般二叉树无奈依据一种序列重构的起因是只晓得根节点，无奈辨别左右子树。如果是二叉搜寻树，那么就有可能依据 一种遍历序列 结构进去。起因就在于二叉搜寻树的根节点的值大于所有的左子树的值，且小于所有的右子树的值。因而咱们能够依据这一个性去确定左右子树的地位，通过这样的转换就和下面的一般二叉树没有啥区别了。比方 1008. 前序遍历结构二叉搜寻树

下面介绍了两种常见的题型：搜寻类和构建类。还有一种比例绝对比拟小的题目类型是批改类。

当然批改类的题目也是要基于搜索算法的，不找到指标怎么删呢？

批改类的题目有两种根本类型。

一种是题目让你减少，删除节点，或者是批改节点的值或者指向。

批改指针的题目个别不难，比方 116. 填充每个节点的下一个右侧节点指针，这不就是 BFS 的时候顺便记录一下上一次拜访的同层节点，而后减少一个指针不就行了么？对于 BFS，套用我的 带层的 BFS 模板 就搞定了。

减少和删除的题目个别略微简单，比方 450. 删除二叉搜寻树中的节点和 669. 修剪二叉搜寻树。西法我教你两个套路，面对这种问题就不带怕的。那就是 后续遍历 + 虚构节点，这两个技巧同样放在前面的七个技巧局部解说。是不是对七个技巧很期待？^\_^

理论工程中，咱们也能够不删除节点，而是给节点做一个标记，示意曾经被删除了，这叫做软删除。

另外一种是为了不便计算，本人加了一个指针。

比方 863. 二叉树中所有间隔为 K 的结点通过批改树的节点类，减少一个指向父节点的援用 parent，问题就转化为间隔指标节点肯定间隔的问题了，此时可是用我下面讲的 带层的 BFS 模板 解决。

动静语言能够间接加属性（比方下面的 parent），而动态语言是不容许的，因而你须要减少一个新的类定义。不过你也能够应用字典来实现，key 是 node 援用，value 是你想记录的货色，比方这里的 parent 节点。

比方对于 Java 来说，咱们能够：

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);
        }
    }
}

简略回顾一下这一大节的常识。

接下来是做树的题目不得不知的四个重要概念。

二叉搜寻树（Binary Search Tree），亦称二叉查找树。

二叉搜寻树具备下列性质的二叉树：

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

对于一个二叉查找树，惯例操作有 插入，查找，删除，找父节点，求最大值，求最小值。

二叉查找树，之所以叫查找树就是因为其非常适合查找。

举个例子，如下一颗二叉查找树，咱们想找节点值小于且最靠近 58 的节点，搜寻的流程如图所示：

（图片来自 https://www.geeksforgeeks.org…）

能够看出每次向下走，都会排除了一个分支，如果一颗二叉搜寻树同时也是一颗二叉均衡树的话，那么其搜寻过程工夫复杂度就是 $O(logN)$。实际上，均衡二叉搜寻树的查找和有序数组的二分查找实质都是一样的，只是数据的存储形式不同罢了。那为什么有了有序数组二分，还须要二叉搜寻树呢？起因在于树的构造对于动态数据比拟优敌对，比方数据是频繁变动的，比方常常增加和删除，那么就能够应用二叉搜寻树。实践上增加和删除的工夫复杂度都是 $O(h)$，其中 h 为树的高度，如果是一颗均衡二叉搜寻树，那么工夫复杂度就是 $O(logN)$。而数组的增加和删除的工夫复杂度为 $O(N)$，其中 N 为数组长度。

不便搜寻，是二叉搜寻树外围的设计初衷。不让查找算法工夫复杂度进化到线性是均衡二叉树的初衷。

咱们平时说的二分很多是数组的二分，因为数组能够随机拜访嘛。不过这种二分切实太广义了，二分的实质是将问题规模放大到一半，因而二分和数据结构没有实质关系，然而不同的数据结构却给二分赋予了不同的色调。比方跳表就是链表的二分，二叉搜寻树就是树的二分等。随着大家对算法和数据结构的理解的加深，会发现更多有意思的货色 ^\_^

另外二叉查找树有一个性质，这个性质对于做题很多帮忙，那就是：二叉搜寻树的中序遍历的后果是一个有序数组 。比方 98. 验证二叉搜寻树就能够间接中序遍历，并 一边遍历一边判断遍历后果是否是枯燥递增的，如果不是则提前返回 False 即可。

再比方 99. 复原二叉搜寻树，官网难度为艰难。题目粗心是 给你二叉搜寻树的根节点 root，该树中的两个节点被谬误地替换。请在不扭转其构造的状况下，复原这棵树。 咱们能够先中序遍历发现不是递增的节点，他们就是被谬误替换的节点，而后替换复原即可。这道题难点就在于一点，即谬误替换可能谬误替换了中序遍历的相邻节点或者中序遍历的非相邻节点，这是两种 case，须要别离探讨。

相似的题目很多，不再赘述。大家如果 碰到二叉搜寻树的搜寻类题目，肯定先想下能不能利用这个性质来做。

一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的程序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的地位雷同，则这棵二叉树称为齐全二叉树。

如下就是一颗齐全二叉树：

间接考查齐全二叉树的题目尽管不多，貌似只有一道 222. 齐全二叉树的节点个数（二分可解），然而了解齐全二叉树对你做题其实帮忙很大。

如上图，是一颗一般的二叉树。如果我将其中的空节点补充齐全，那么它就是一颗齐全二叉树了。

这有什么用呢？这很有用！我总结了两个用途：

咱们能够给齐全二叉树编号，这样父子之间就能够通过编号轻松求出。比方我给所有节点从左到右从上到下顺次从 1 开始编号。那么已知一个节点的编号是 i，那么其左子节点就是 2 i，右子节点就是 2 1 + 1，父节点就是 (i + 1) / 2。

相熟二叉堆的同学可能发现了，这就是用数组实现的二叉堆，其实 二叉堆就是齐全二叉树的一个利用。

有的同学会说，”然而很多题目都不是齐全二叉树呀，那不是用不上了么？“其实不然，咱们只有设想它存在即可，咱们将空节点脑补上去不就能够了？比方 662. 二叉树最大宽度。题目形容：

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）构造雷同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。示例 1:

输出:

           1
         /   \
        3     2
       / \     \
      5   3     9

输入: 4
解释: 最大值呈现在树的第 3 层，宽度为 4 (5,3,null,9)。

很简略，一个带层的 BFS 模板即可搞定，几乎就是默写题。不过这里须要留神两点：

入队的时候除了要将一般节点入队，还要空节点入队。
出队的时候除了入队节点自身，还要将节点的地位信息入队，即下方代码的 pos。

参考代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

再比方剑指 Offer 37. 序列化二叉树。如果我将一个二叉树的齐全二叉树模式序列化，而后通过 BFS 反序列化，这不就是力扣官网序列化树的形式么？比方：

序列化为 “[1,2,3,null,null,4,5]”。这不就是我刚刚画的齐全二叉树么？就是将一个一般的二叉树硬生生当成齐全二叉树用了。

其实这并不是序列化成了齐全二叉树，上面会纠正。

将一颗一般树序列化为齐全二叉树很简略，只有将空节点当成一般节点入队解决即可。代码：

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 即可。

你只有彻底了解我方才讲的 咱们能够给齐全二叉树编号，这样父子之间就能够通过编号轻松求出。比方我给所有节点从左到右从上到下顺次从 1 开始编号。那么已知一个节点的编号是 i，那么其左子节点就是 2 * i，右子节点就是 2 * 1 + 1，父节点就是 (i + 1) / 2。 这句话，那么反序列化对你就不是难事。

如果我用一个箭头示意节点的父子关系，箭头指向节点的两个子节点，那么大略是这样的：

咱们方才提到了：

1 号节点的两个子节点的 2 号和 3 号。
2 号节点的两个子节点的 4 号和 5 号。
。。。
i 号节点的两个子节点的 2 * i 号和 2 * 1 + 1 号。

此时你可能会写出相似这样的代码：

    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

这个题目尽管并不是齐全二叉树的题目，然而却和齐全二叉树很像，有借鉴齐全二叉树的中央。

对于门路这个概念，leetcode 真的挺喜爱考查的，不信你本人去 leetcode 官网搜寻一下门路，看有多少题。树的门路这种题目的变种很多，算是一种经典的考点了。

要明确门路的概念，以及如何解决这种题，只须要看一个题目就好了 124. 二叉树中的最大门路和，尽管是艰难难度，然而搞清楚概念的话，和简略难度没啥区别。接下来，咱们就以这道题解说一下。

这道题的题目是 给定一个非空二叉树，返回其最大门路和 。门路的概念是： 一条从树中任意节点登程，沿父节点 - 子节点连贯，达到任意节点的序列。该门路至多蕴含一个节点，且不肯定通过根节点。这听起来真的不容易了解，力扣给的 demo 我也没搞懂，这里我本人画了几个图来给大家解释一下这个概念。

首先是官网给的两个例子：

接着是我本人画的一个例子：

如图红色的局部是最大门路上的节点。

能够看出：

门路能够由一个节点做成，能够由两个节点组成，也能够由三个节点组成等等，然而必须间断。
门路必须是”直来直去“的，不能拐。比方上图的门路的左下角是 3，就不能是 2，因为如果是 2 就拐了。

咱们持续回到 124 题。题目说是”从任意节点登程 …….“看完这个形容我会想到大概率是要么全局记录最大值，要么双递归。

如果应用双递归，那么复杂度就是 $O(N^2)$，实际上，子树的门路和计算出来了，能够推导出父节点的最大门路和，因而如果应用双递归会有反复计算。一个可行的形式是记忆化递归。
如果应用全局记录最大值，只须要在递归的时候 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

相似题目 113. 门路总和 I

和门路相似，间隔也是一个类似且频繁呈现的一个考点，并且二者都是搜寻类题目的考点。起因就在于最短门路就是间隔，而树的最短门路就是边的数目。

这两个题练习一下，碰到间隔的题目根本就稳了。

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

下面数次提到了七个技巧，置信大家曾经急不可待想要看看这七个技巧了吧。那就让我拿出本章压箱底的内容吧~

留神，这七个技巧全副是基于 dfs 的，bfs 把握了模板就行，根本没有什么技巧可言。

认真学习的小伙伴能够发现了，下面的内容只有 二叉树的迭代写法（双色标记法） 和 两个 BFS 模板 具备实操性，其余大多是战略思想上的。算法思维诚然重要，然而要联合具体实际落地能力有实际价值，能力让咱们把常识消化成本人的。而这一节满满的全是实用干货ヽ(~ ω ~(~ ω ~〃) ゝ。

第一个技巧，也是最容易把握的一个技巧。咱们写力扣的树题目的时候，函数的入参全都是叫 root。而这个技巧是说，咱们在写 dfs 函数的时候，要将函数中示意以后节点的形参也写成 root。即：

def dfs(root):
    # your code

而之前我始终习惯写成 node，即：

def dfs(node):
    # your code

可能有的同学想问：”这有什么关系么？“。我总结了两个起因。

第一个起因是：以前 dfs 的形参写的是 node，而我常常误写成 root，导致出错（这个谬误并不会抛错，因而不是特地容易发现）。自从换成了 root 就没有产生这样的问题了。

第二个起因是：这样写相当于把 root 当成是 current 指针来用了。最开始 current 指针指向 root，而后一直批改指向树的其它节点。这样就概念就简化了，只有一个以后指针的概念。如果应用 node，就是以后指针 + root 指针两个概念了。

（一开始 current 就是 root）

（前面 current 一直扭转。具体如何扭转，取决于你的搜索算法，是 dfs 还是 bfs 等）

下面的技巧稍显简略，然而却有用。这里介绍一个略微难一点的技巧，也更加有用。

咱们晓得递归是一个很有用的编程技巧，灵便应用递归，能够使本人的代码更加简洁，简洁意味着代码不容易出错，即便出错了，也能及时发现问题并修复。

树的题目大多数都能够用递归轻松地解决。如果一个递归不行，那么来两个。（至今没见过三递归或更多递归）

单递归大家写的比拟多了，其实本篇文章的大部分递归都是单递归。那什么时候须要两个递归呢？其实我下面曾经提到了，那就是 如果题目有相似，任意节点开始 xxxx 或者所有 xxx这样的说法，就能够思考应用双递归。然而如果递归中有反复计算，则能够应用双递归 + 记忆化或者间接单递归。

比方面试题 04.12. 求和门路，再比方 563. 二叉树的坡度这两道题的题目说法都能够思考应用双递归求解。

双递归的根本套路就是一个主递归函数和一个外部递归函数。主递归函数负责计算以某一个节点开始的 xxxx，外部递归函数负责计算 xxxx，这样就实现了以 所有节点开始的 xxxx。

其中 xxx 能够替换成任何题目形容，比方门路和等

一个典型的加法双递归是这样的：

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 指针，因而只有两种遍历。而二叉树有两个指针，因而常见的遍历有三个，除了前后序，还有一个中序。而中序除了二叉搜寻树，其余中央用的并不多。

和链表一样，要把握树的前后序，也只须要记住一句话就好了。那就是 如果是前序遍历，那么你能够设想下面的节点都解决好了，怎么解决的不必管 。相应地 如果是后序遍历，那么你能够设想上面的树都解决好了，怎么解决的不必管。这句话的正确性也是毋庸置疑。

前后序对链表来说比拟直观。对于树来说，其实更形象地说应该是自顶向下或者自底向上。自顶向下和自底向上在算法上是不同的，不同的写法有时候对应不同的书写难度。比方 https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/，这种题目就适宜通过参数扩大 + 前序来实现。

对于参数扩大的技巧，咱们在前面开展。

自顶向下 就是在每个递归层级，首先拜访节点来计算一些值，并在递归调用函数时将这些值传递到子节点，个别是 通过参数传到子树 中。
自底向上 是另一种常见的递归办法，首先对所有子节点递归地调用函数，而后依据 返回值 和根节点自身 的值得到答案。

对于前后序的思维技巧，能够参考我的这个文章的 前后序局部。

总结下我的教训：

大多数树的题应用后序遍历比较简单，并且大多须要依赖左右子树的返回值。比方 1448. 统计二叉树中好节点的数目
不多的问题须要前序遍历，而前序遍历通常要联合参数扩大技巧。比方 1022. 从根到叶的二进制数之和
如果你能应用参数和节点自身的值来决定什么应该是传递给它子节点的参数，那就用前序遍历。
如果对于树中的任意一个节点，如果你晓得它子节点的答案，你能计算出以后节点的答案，那就用后序遍历。
如果遇到二叉搜寻树则思考中序遍历

是的！不仅仅链表有虚构节点的技巧，树也是一样。对于这点大家可能比拟容易漠视。

回顾一下链表的虚构指针的技巧，咱们通常在什么时候才会应用？

其中一种状况是 链表的头会被批改。这个时候通常须要一个虚构指针来做新的头指针，这样就不须要思考第一个指针的问题了（因为此时第一个指针变成了咱们的虚构指针，而虚构指针是不必参加题目运算的）。树也是一样，当你须要对树的头节点（在树中咱们称之为根节点）进行批改的时候，就能够思考应用虚构指针的技巧了。
另外一种是题目须要返回树两头的某个节点（不是返回根节点）。实际上也可借助虚构节点。因为我下面提到的指针的操作，实际上，你能够新建一个虚构头，而后让虚构头在失当的时候（刚好指向须要返回的节点）断开连接，这样咱们就能够返回虚构头的 next 就 ok 了。

更多对于虚构指针的技巧能够参考这个文章的 虚构头局部。

上面就力扣中的两道题来看一下。

题目形容：

给定二叉树根结点 root，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不蕴含 1 的子树的原二叉树。(节点 X 的子树为 X 自身，以及所有 X 的后辈。)

示例 1:
输出: [1,null,0,0,1]
输入: [1,null,0,null,1]

解释:
只有红色节点满足条件“所有不蕴含 1 的子树”。右图为返回的答案。



示例 2:
输出: [1,0,1,0,0,0,1]
输入: [1,null,1,null,1]

示例 3:
输出: [1,1,0,1,1,0,1,0]
输入: [1,1,0,1,1,null,1]

阐明:

给定的二叉树最多有 100 个节点。每个节点的值只会为 0 或 1。

依据题目形容不难看出，咱们的根节点可能会被整个移除掉。这就是我下面说的 根节点被批改 的状况。这个时候，咱们只有新建一个虚构节点当做新的根节点，就不须要思考这个问题了。

此时的代码是这样的：

var pruneTree = function (root) {function dfs(root) {// do something}
  ans = new TreeNode(-1);
  ans.left = root;
  dfs(ans);
  return ans.left;
};

接下来，只须要欠缺 dfs 框架即可。dfs 框架也很容易，咱们只须要将子树和为 0 的节点移除即可，而计算子树和是一个难度为 easy 的题目，只须要后序遍历一次并收集值即可。

计算子树和的代码如下:

function dfs(root) {if (!root) return 0;
  const l = dfs(root.left);
  const r = dfs(root.right);
  return root.val + l + r;
}

有了下面的铺垫，最终代码就不难写出了。

残缺代码(JS)：

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;
};

题目形容：

给你一棵以 root 为根的二叉树和一个整数 target，请你删除所有值为 target 的 叶子节点。留神，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target，那么这个节点也应该被删除。也就是说，你须要反复此过程直到不能持续删除。示例 1：



输出：root = [1,2,3,2,null,2,4], target = 2
输入：[1,null,3,null,4]
解释：下面右边的图中，绿色节点为叶子节点，且它们的值与 target 雷同（同为 2），它们会被删除，失去两头的图。有一个新的节点变成了叶子节点且它的值与 target 雷同，所以将再次进行删除，从而失去最左边的图。示例 2：



输出：root = [1,3,3,3,2], target = 3
输入：[1,3,null,null,2]
示例 3：



输出：root = [1,2,null,2,null,2], target = 2
输入：[1]
解释：每一步都删除一个绿色的叶子节点（值为 2）。示例 4：输出：root = [1,1,1], target = 1
输入：[]
示例 5：输出：root = [1,2,3], target = 1
输入：[1,2,3]
 

提醒：1 <= target <= 1000
每一棵树最多有 3000 个节点。每一个节点值的范畴是 [1, 1000]。

和下面题目相似，这道题的根节点也可能被删除，因而这里咱们采取和下面题目相似的技巧。

因为题目阐明了一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target，那么这个节点也应该被删除。也就是说，你须要反复此过程直到不能持续删除。因而这里应用后序遍历会比拟容易，因为形象地看下面的形容过程你会发现这是一个自底向上的过程，而自底向上通常用后序遍历。

下面的题目，咱们能够依据子节点的返回值决定是否删除子节点。而这道题是依据左右子树是否为空，删除本人，关键字是本人。而树的删除和链表删除相似，树的删除须要父节点，因而这里的技巧和链表相似，记录一下以后节点的父节点即可，并通过 参数扩大 向下传递。至此，咱们的代码大略是：

class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
        # 单链表只有一个 next 指针，而二叉树有两个指针 left 和 right，因而要记录一下以后节点是其父节点的哪个孩子
        def dfs(node, parent, is_left=True):
            # do something
        ans = TreeNode(-1)
        ans.left = root
        dfs(root, ans)
        return ans.left

有了下面的铺垫，最终代码就不难写出了。

残缺代码（Python）:

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('是空节点，你须要返回适合的值')
    # your code here`

叶子节点

伪代码：

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

一张图总结一下：

通过这样的解决，前面的代码根本都不须要判空了。

相比于搜寻类，构建就比拟麻烦了。我总结了两个常见的边界。

参数扩大的边界

比方 1008 题，依据前序遍历结构二叉搜寻树。我就少思考的边界。

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:
            return None

        root.left = dfs(start + 1, mid - 1)
        root.right = dfs(mid, end)
        return root

    return dfs(0, len(preorder) - 1)

留神下面的代码没有判断 start == end 的状况，加上面这个判断就好了。

if start == end: return TreeNode(preorder[start])

虚构节点

除了搜寻类的技巧能够用于构建类外，也能够思考用我下面的讲的虚构节点。

参数扩大这个技巧十分好用，一旦把握你会爱不释手。

如果不思考参数扩大，一个最简略的 dfs 通常是上面这样：

def dfs(root):
    # do something

而有时候，咱们须要 dfs 携带更多的有用信息。典型的有以下三种状况：

携带父亲或者爷爷的信息。

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

携带门路信息，能够是门路和或者具体的门路数组等。

门路和：

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. 求和门路来练练手。

以上几个模板都很常见，相似的场景还有很多。总之当你须要传递额定信息给子节点（关键字是子节点）的时候，请务必把握这种技巧。这也解释了为啥参数扩大常常用于前序遍历。

二叉搜寻树的搜寻题大多数都须要扩大参考，甚至怎么扩大都是固定的。

二叉搜寻树的搜寻总是将最大值和最小值通过参数传递到左右子树，相似 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. 节点与其先人之间的最大差值, 题目粗心是：给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val – B.val|，且 A 是 B 的先人。

应用相似下面的套路轻松求解。

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 返回数组比拟少见。即便题目要求返回数组，咱们也通常是申明一个数组，在 dfs 过程一直 push，最终返回这个数组。而不会抉择返回一个数组。绝大多数状况下，返回数组是用于计算笛卡尔积。因而你须要用到笛卡尔积的时候，思考应用返回数组的形式。

一般来说，如果须要应用笛卡尔积的状况还是比拟容易看出的。另外一个不太精确的技巧是，如果题目有”所有可能“，”所有状况“，能够思考应用此技巧。

一个典型的题目是 1530. 好叶子节点对的数量

题目形容：

给你二叉树的根节点 root 和一个整数 distance。如果二叉树中两个叶节点之间的 最短门路长度 小于或者等于 distance，那它们就能够形成一组 好叶子节点对。返回树中 好叶子节点对的数量。示例 1：

 



输出：root = [1,2,3,null,4], distance = 3
输入：1
解释：树的叶节点是 3 和 4，它们之间的最短门路的长度是 3。这是惟一的好叶子节点对。示例 2：


输出：root = [1,2,3,4,5,6,7], distance = 3
输入：2
解释：好叶子节点对为 [4,5] 和 [6,7]，最短门路长度都是 2。然而叶子节点对 [4,6] 不满足要求，因为它们之间的最短门路长度为 4。示例 3：输出：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输入：1
解释：惟一的好叶子节点对是 [2,5]。示例 4：输出：root = [100], distance = 1
输入：0
示例 5：输出：root = [1,1,1], distance = 2
输入：1
 

提醒：tree 的节点数在 [1, 2^10] 范畴内。每个节点的值都在 [1, 100] 之间。1 <= distance <= 10

下面咱们学习了门路的概念，在这道题又用上了。

其实两个叶子节点的最短门路（间隔）能够用其最近的公共先人来辅助计算。即 两个叶子节点的最短门路 = 其中一个叶子节点到最近公共先人的间隔 + 另外一个叶子节点到最近公共先人的间隔。

因而咱们能够定义 dfs(root)，其性能是计算以 root 作为出发点，到其各个叶子节点的间隔。如果其子节点有 8 个叶子节点，那么就返回一个长度为 8 的数组，数组每一项的值就是其到对应叶子节点的间隔。

如果子树的后果计算出来了，那么父节点只须要把子树的每一项加 1 即可。这点不难理解，因为 父到各个叶子节点的间隔就是父节点到子节点的间隔（1）+ 子节点到各个叶子节点的间隔。

由下面的推导可知须要先计算子树的信息，因而咱们抉择前序遍历。

残缺代码（Python）：

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. 后继者

树的题目一种中心点就是遍历，这是搜寻问题和批改问题的根底。

而遍历从大的方向分为 广度优先遍历和深度优先遍历 ，这就是咱们的 两个基本点。两个基本点能够进一步细分，比方广度优先遍历有带层信息的和不带层信息的（其实只有会带层信息的就够了）。深度优先遍历常见的是前序和后序，中序多用于二叉搜寻树，因为二叉搜寻树的中序遍历是严格递增的数组。

树的题目从大的方向上来看就三种，一种是搜寻类，这类题目最多，这种题目牢牢把握 开始点，完结点和指标即可 。构建类型的题目我之前的专题以及讲过了，一句话概括就是 依据一种遍历后果确定根节点地位，依据另外一种遍历后果（如果是二叉搜寻树就不须要了）确定左右子树。批改类题目不多，这种问题边界须要非凡思考，这是和搜寻问题的本质区别，能够应用虚构节点技巧。另外搜寻问题，如果返回值不是根节点也能够思考虚构节点。

树有四个比拟重要的对做题帮忙很大的概念，别离是齐全二叉树，二叉搜寻树，门路和间隔，这外面相干的题目举荐大家好好做一下，都很经典。

最初我给大家介绍了七种干货技巧，很多技巧都阐明了在什么状况下能够应用。好不好用你本人去找几个题目试试就晓得了。

以上就是树专题的全部内容了。大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 38K star 啦。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

我整顿的 1000 多页的电子书曾经开发下载了，大家能够去我的公众号《力扣加加》后盾回复电子书获取。

一点絮叨

食用指南

前言

基本概念

二叉树

二叉树分类

二叉树的示意

树题难度几何？

一个核心

树的遍历迭代写法

小结

两个基本点

BFS 不是 档次遍历

深度优先遍历

算法流程

算法模板

两种常见分类

前序遍历

后续遍历

递归遍历的学习技巧

广度优先遍历

算法流程

算法模板

两种常见分类

标记层

不标记层

小结

三种题型

搜寻类

DFS 搜寻

BFS 搜寻

构建类

一般二叉树的构建

二叉搜寻树的构建

批改类

题目要求的批改

算法须要，本人批改

四个重要概念

二叉搜寻树

天生适宜查找

中序遍历是有序的

齐全二叉树

门路

间隔

七个技巧

dfs(root)

单 / 双递归

前后遍历

虚构节点

【题目一】814. 二叉树剪枝

【题目一】1325. 删除给定值的叶子节点

边界

搜寻类

构建类

参数扩大大法

返回元组 / 列表

返回元祖

返回数组

经典题目

总结

BFS 不是档次遍历