AI summary
type
status
date
slug
summary
category
tags
icon
password
先在开头总结一下，二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
本文中会用题目来举例，但都是最最简单的题目，所以不用担心自己看不懂，我可以帮你从最简单的问题中提炼出所有二叉树题目的共性，并将二叉树中蕴含的思维进行升华，反手用到 动态规划，回溯算法，分治算法，图论算法 中去，这也是我一直强调框架思维的原因。希望你在学习了上述高级算法后，也能回头再来看看本文，会对它们有更深刻的认识。
首先，我还是要不厌其烦地强调一下二叉树这种数据结构及相关算法的重要性。

二叉树的重要性

举个例子，比如两个经典排序算法 快速排序 和 归并排序，对于它俩，你有什么理解？
如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了。
为什么快速排序和归并排序能和二叉树扯上关系？我们来简单分析一下他们的算法思想和代码框架：
快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
快速排序的代码框架如下：
先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？
再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。
归并排序的代码框架如下：
先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛，不过如此呀。
如果你一眼就识破这些排序算法的底细，还需要背这些经典算法吗？不需要。你可以手到擒来，从二叉树遍历框架就能扩展出算法了。
说了这么多，旨在说明，二叉树的算法思想的运用广泛，甚至可以说，只要涉及递归，都可以抽象成二叉树的问题。
接下来我们从二叉树的前中后序开始讲起，让你深刻理解这种数据结构的魅力。

深入理解前中后序

单链表和数组的遍历可以是迭代的，也可以是递归的，二叉树这种结构无非就是二叉链表，它没办法简单改写成 for 循环的迭代形式，所以我们遍历二叉树一般都使用递归形式。
你也注意到了，只要是递归形式的遍历，都可以有前序位置和后序位置，分别在递归之前和递归之后。
所谓前序位置，就是刚进入一个节点（元素）的时候，后序位置就是即将离开一个节点（元素）的时候，那么进一步，你把代码写在不同位置，代码执行的时机也不同。
比如说，如果让你倒序打印一条单链表上所有节点的值，你怎么搞？
实现方式当然有很多，但如果你对递归的理解足够透彻，可以利用后序位置来操作，本质上是利用递归的堆栈：
那么说回二叉树也是一样的，只不过多了一个中序位置罢了。
二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。
你也可以看到，图论算法基础 把二叉树的遍历框架扩展到了图，并以遍历为基础实现了图论的各种经典算法，不过这是后话，本文就不多说了。

两种解题思路

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着「回溯算法核心框架」和「动态规划核心框架」。
这里说一下我的函数命名习惯：二叉树中用遍历思路解题时函数签名一般是 void traverse(...)，没有返回值，靠更新外部变量来计算结果，而用分解问题思路解题时函数名根据该函数具体功能而定，而且一般会有返回值，返回值是子问题的计算结果。
虽然函数命名没有什么硬性的要求，但我还是建议你也遵循我的这种风格，这样更能突出函数的作用和解题的思维模式，便于你自己理解和运用。

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
你做这题的思路是什么？显然遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度，这就是遍历二叉树计算答案的思路。
解法代码如下：
这个解法应该很好理解，但为什么需要在前序位置增加 depth，在后序位置减小 depth？
因为前面说了，前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，depth 记录当前递归到的节点深度，你把 traverse 理解成在二叉树上游走的一个指针，所以当然要这样维护。
当然，你也很容易发现一棵二叉树的最大深度可以通过子树的最大深度推导出来，这就是分解问题计算答案的思路。
解法代码如下：
只要明确递归函数的定义，这个解法也不难理解，但为什么主要的代码逻辑集中在后序位置？
因为这个思路正确的核心在于，你确实可以通过子树的最大深度推导出原树的深度，所以当然要首先利用递归函数的定义算出左右子树的最大深度，然后推出原树的最大深度，主要逻辑自然放在后序位置。
如果你理解了最大深度这个问题的两种思路，那么我们再回头看看最基本的二叉树前中后序遍历，就比如力扣第 144 题「二叉树的前序遍历」，让你计算前序遍历结果。

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
我们熟悉的解法就是用「遍历」的思路，我想应该没什么好说的：
但你是否能够用「分解问题」的思路，来计算前序遍历的结果？
换句话说，不要用像 traverse 这样的辅助函数和任何外部变量，单纯用题目给的 preorderTraverse 函数递归解题，你会不会？
分解问题：一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果。
所以，你可以这样实现前序遍历算法：
中序和后序遍历也是类似的，只要把 add(root.val) 放到中序和后序对应的位置就行了。
这个解法短小精干，但为什么不常见呢？
一个原因是这个算法的复杂度不好把控，比较依赖语言特性。
Java 的话无论 ArrayList 还是 LinkedList，addAll 方法的复杂度都是 O(N)，所以总体的最坏时间复杂度会达到 O(N^2)，除非你自己实现一个复杂度为 O(1) 的 addAll 方法，底层用链表的话是可以做到的，因为多条链表只要简单的指针操作就能连接起来。
当然，最主要的原因还是因为教科书上从来没有这么教过……

后序位置的特殊之处

说后序位置之前，先简单说下前序和中序。
前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。
中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。
仔细观察，前中后序位置的代码，能力依次增强。
前序位置的代码只能从函数参数中获取父节点传递来的数据。
中序位置的代码不仅可以获取参数数据，还可以获取到左子树通过函数返回值传递回来的数据。
后序位置的代码最强，不仅可以获取参数数据，还可以同时获取到左右子树通过函数返回值传递回来的数据。
所以，某些情况下把代码移到后序位置效率最高；有些事情，只有后序位置的代码能做。
举些具体的例子来感受下它们的能力区别。现在给你一棵二叉树，我问你两个简单的问题：
  1. 如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
  1. 如何打印出每个节点的左右子树各有多少节点？
这两个问题的根本区别在于：
一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你必须遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。
结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
解决这题的关键在于，每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。
把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的。
解法代码如下：
时间复杂度为 maxDepth 函数的 O(N)
讲到这里，照应一下前文：遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
请你思考一下，运用后序遍历的题目使用的是「遍历」的思路还是「分解问题」的思路？
答：利用后序位置的题目，一般都使用「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。

以树的视角看动归/回溯/DFS算法的区别和联系

前文我说动态规划/回溯算法就是二叉树算法两种不同思路的表现形式，相信能看到这里的读者应该也认可了我这个观点。但有细心的读者经常提问：你的思考方法让我豁然开朗，但你好像一直没讲过 DFS 算法？
其实我在 一文秒杀所有岛屿题目 中就是用的 DFS 算法，但我确实没有单独用一篇文章讲 DFS 算法，因为 DFS 算法和回溯算法非常类似，只是在细节上有所区别。
这个细节上的差别是什么呢？其实就是「做选择」和「撤销选择」到底在 for 循环外面还是里面的区别，DFS 算法在外面，回溯算法在里面。
为什么有这个区别？还是要结合着二叉树理解。这一部分我就把回溯算法、DFS 算法、动态规划三种经典的算法思想，以及它们和二叉树算法的联系和区别，用一句话来说明：
动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：
  • 动态规划算法属于分解问题（分治）的思路，它的关注点在整棵「子树」。
  • 回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
  • DFS 算法属于遍历的思路，它的关注点在单个「节点」。
怎么理解？我分别举三个例子你就懂了。

分解问题的思想

第一个例子，给你一棵二叉树，请你用分解问题的思路写一个 count 函数，计算这棵二叉树共有多少个节点。代码很简单，上文都写过了：
你看，这就是动态规划分解问题的思路，它的着眼点永远是结构相同的整个子问题，类比到二叉树上就是「子树」。

回溯算法的思想

第二个例子，给你一棵多叉树，请你用遍历的思路写一个 traverse 函数，打印出遍历的过程，你看下代码：
这个多叉树的遍历框架就可以延伸出 回溯算法框架套路详解 中的回溯算法框架：
你看，这就是回溯算法遍历的思路，它的着眼点永远是在节点之间移动的过程，类比到二叉树上就是「树枝」。

DFS 的思想

第三个例子，我给你一棵二叉树，请你写一个 traverse 函数，把这棵二叉树上的每个节点的值都加一。很简单吧，代码如下：
你看，这就是 DFS 算法遍历的思路，它的着眼点永远是在单一的节点上，类比到二叉树上就是处理每个「节点」。
有了这些铺垫，你就很容易理解为什么回溯算法和 DFS 算法代码中「做选择」和「撤销选择」的位置不同了，看下面两段代码：

层序遍历

二叉树题型主要是用来培养递归思维的，而层序遍历属于迭代遍历，也比较简单，这里就过一下代码框架吧：
这里面 while 循环和 for 循环分管从上到下和从左到右的遍历：
notion image