跳至主要內容

 

labuladong原创数据结构二叉树分解问题的思路遍历的思路核心框架约 9619 字大约 32 分钟

Info

新版网站会员open in new window 限时优惠；算法可视化编辑器上线，点击体验open in new window！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode力扣难度
104. Maximum Depth of Binary Treeopen in new window104. 二叉树的最大深度open in new window🟢
144. Binary Tree Preorder Traversalopen in new window144. 二叉树的前序遍历open in new window🟢
543. Diameter of Binary Treeopen in new window543. 二叉树的直径open in new window🟢
-剑指 Offer 55 - I. 二叉树的深度open in new window🟢

Tip

本文有视频版：二叉树/递归的框架思维（纲领篇）open in new window。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

我的公众号历史文章的整个脉络都是按照 学习数据结构和算法的框架思维 提出的框架来构建的，其中着重强调了二叉树题目的重要性，所以把本文放在第一章的必读系列中。

我刷了这么多年题，浓缩出二叉树算法的一个总纲放在这里，也许用词不是特别专业化，也没有什么教材会收录我的这些经验总结，但目前各个刷题平台的题库，没有一道二叉树题目能跳出本文划定的框架。如果你能发现一道题目和本文给出的框架不兼容，请留言告知我。

先在开头总结一下，二叉树解题的思维模式分两类：

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] 中寻找新的分界点，最后整个数组就被排序了。

快速排序的代码框架如下：

java 🟢
void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？

再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。

归并排序的代码框架如下：

java 🟢
// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // 排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    /****** 后序位置 ******/
    // 合并 nums[lo..mid] 和 nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    /*********************/
}

先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛，不过如此呀。

如果你一眼就识破这些排序算法的底细，还需要背这些经典算法吗？不需要。你可以手到擒来，从二叉树遍历框架就能扩展出算法了。

说了这么多，旨在说明，二叉树的算法思想的运用广泛，甚至可以说，只要涉及递归，都可以抽象成二叉树的问题。

接下来我们从二叉树的前中后序开始讲起，让你深刻理解这种数据结构的魅力。

深入理解前中后序

我先甩给你几个问题，请默默思考 30 秒：

1、你理解的二叉树的前中后序遍历是什么，仅仅是三个顺序不同的 List 吗？

2、请分析，后序遍历有什么特殊之处？

3、请分析，为什么多叉树没有中序遍历？

答不上来，说明你对前中后序的理解仅仅局限于教科书，不过没关系，我用类比的方式解释一下我眼中的前中后序遍历。

首先，回顾一下 学习数据结构和算法的框架思维 中说到的二叉树遍历框架：

java 🟢
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

先不管所谓前中后序，单看 traverse 函数，你说它在做什么事情？

其实它就是一个能够遍历二叉树所有节点的一个函数，和你遍历数组或者链表本质上没有区别：

java 🟢
/* 迭代遍历数组 */
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {

    }
}

/* 递归遍历数组 */
void traverse(int[] arr, int i) {
    if (i == arr.length) {
        return;
    }
    // 前序位置
    traverse(arr, i + 1);
    // 后序位置
}

/* 迭代遍历单链表 */
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {

    }
}

/* 递归遍历单链表 */
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    // 前序位置
    traverse(head.next);
    // 后序位置
}

单链表和数组的遍历可以是迭代的，也可以是递归的，二叉树这种结构无非就是二叉链表，由于没办法简单改写成迭代形式，所以一般说二叉树的遍历框架都是指递归的形式。

你也注意到了，只要是递归形式的遍历，都可以有前序位置和后序位置，分别在递归之前和递归之后。

所谓前序位置，就是刚进入一个节点（元素）的时候，后序位置就是即将离开一个节点（元素）的时候，那么进一步，你把代码写在不同位置，代码执行的时机也不同：

比如说，如果让你倒序打印一条单链表上所有节点的值，你怎么搞？

实现方式当然有很多，但如果你对递归的理解足够透彻，可以利用后序位置来操作：

java 🟢
/* 递归遍历单链表，倒序打印链表元素 */
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    traverse(head.next);
    // 后序位置
    print(head.val);
}

结合上面那张图，你应该知道为什么这段代码能够倒序打印单链表了吧，本质上是利用递归的堆栈帮你实现了倒序遍历的效果。

那么说回二叉树也是一样的，只不过多了一个中序位置罢了。

教科书里只会问你前中后序遍历结果分别是什么，所以对于一个只上过大学数据结构课程的人来说，他大概以为二叉树的前中后序只不过对应三种顺序不同的 List<Integer> 列表。

但是我想说，前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：

前序位置的代码在刚刚进入一个二叉树节点的时候执行；

后序位置的代码在将要离开一个二叉树节点的时候执行；

中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

你注意本文的用词，我一直说前中后序「位置」，就是要和大家常说的前中后序「遍历」有所区别：你可以在前序位置写代码往一个 List 里面塞元素，那最后得到的就是前序遍历结果；但并不是说你就不可以写更复杂的代码做更复杂的事。

画成图，前中后序三个位置在二叉树上是这样：

你可以发现每个节点都有「唯一」属于自己的前中后序位置，所以我说前中后序遍历是遍历二叉树过程中处理每一个节点的三个特殊时间点。

这里你也可以理解为什么多叉树没有中序位置，因为二叉树的每个节点只会进行唯一一次左子树切换右子树，而多叉树节点可能有很多子节点，会多次切换子树去遍历，所以多叉树节点没有「唯一」的中序遍历位置。

说了这么多基础的，就是要帮你对二叉树建立正确的认识，然后你会发现：

二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。

你也可以看到，图论算法基础 把二叉树的遍历框架扩展到了图，并以遍历为基础实现了图论的各种经典算法，不过这是后话，本文就不多说了。

两种解题思路

前文 我的算法学习心得 说过：

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。

提示

这里说一下我的函数命名习惯：二叉树中用遍历思路解题时函数签名一般是 void traverse(...)，没有返回值，靠更新外部变量来计算结果，而用分解问题思路解题时函数名根据该函数具体功能而定，而且一般会有返回值，返回值是子问题的计算结果。

与此对应的，你会发现我在 回溯算法核心框架 中给出的函数签名一般也是没有返回值的 void backtrack(...)，而在 动态规划核心框架 中给出的函数签名是带有返回值的 dp 函数。这也说明它俩和二叉树之间千丝万缕的联系。

虽然函数命名没有什么硬性的要求，但我还是建议你也遵循我的这种风格，这样更能突出函数的作用和解题的思维模式，便于你自己理解和运用。

当时我是用二叉树的最大深度这个问题来举例，重点在于把这两种思路和动态规划和回溯算法进行对比，而本文的重点在于分析这两种思路如何解决二叉树的题目。

力扣第 104 题「二叉树的最大深度open in new window」就是最大深度的题目，所谓最大深度就是根节点到「最远」叶子节点的最长路径上的节点数，比如输入这棵二叉树，算法应该返回 3：

你做这题的思路是什么？显然遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度，这就是遍历二叉树计算答案的思路。

解法代码如下：

java 🟢
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;

// 主函数
int maxDepth(TreeNode root) {
	traverse(root);
	return res;
}

// 二叉树遍历框架
void traverse(TreeNode root) {
	if (root == null) {
		return;
	}
	// 前序位置
	depth++;
    if (root.left == null && root.right == null) {
        // 到达叶子节点，更新最大深度
		res = Math.max(res, depth);
    }
	traverse(root.left);
	traverse(root.right);
	// 后序位置
	depth--;
}

这个解法应该很好理解，但为什么需要在前序位置增加 depth，在后序位置减小 depth？

因为前面说了，前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，depth 记录当前递归到的节点深度，你把 traverse 理解成在二叉树上游走的一个指针，所以当然要这样维护。

至于对 res 的更新，你放到前中后序位置都可以，只要保证在进入节点之后，离开节点之前（即 depth 自增之后，自减之前）就行了。

当然，你也很容易发现一棵二叉树的最大深度可以通过子树的最大深度推导出来，这就是分解问题计算答案的思路。

解法代码如下：

java 🟢
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	// 利用定义，计算左右子树的最大深度
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	// 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
	int res = Math.max(leftMax, rightMax) + 1;

	return res;
}

只要明确递归函数的定义，这个解法也不难理解，但为什么主要的代码逻辑集中在后序位置？

因为这个思路正确的核心在于，你确实可以通过子树的最大深度推导出原树的深度，所以当然要首先利用递归函数的定义算出左右子树的最大深度，然后推出原树的最大深度，主要逻辑自然放在后序位置。

如果你理解了最大深度这个问题的两种思路，那么我们再回头看看最基本的二叉树前中后序遍历，就比如算前序遍历结果吧。

我们熟悉的解法就是用「遍历」的思路，我想应该没什么好说的：

java 🟢
List<Integer> res = new LinkedList<>();

// 返回前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
    traverse(root);
    return res;
}

// 二叉树遍历函数
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    res.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

但你是否能够用「分解问题」的思路，来计算前序遍历的结果？

换句话说，不要用像 traverse 这样的辅助函数和任何外部变量，单纯用题目给的 preorderTraverse 函数递归解题，你会不会？

我们知道前序遍历的特点是，根节点的值排在首位，接着是左子树的前序遍历结果，最后是右子树的前序遍历结果：

那这不就可以分解问题了么，一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果。

所以，你可以这样实现前序遍历算法：

java 🟢
// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    // 前序遍历的结果，root.val 在第一个
    res.add(root.val);
    // 利用函数定义，后面接着左子树的前序遍历结果
    res.addAll(preorderTraverse(root.left));
    // 利用函数定义，最后接着右子树的前序遍历结果
    res.addAll(preorderTraverse(root.right));/**<extend up -200><div class="img-content"><img src="/algo/images/二叉树收官/3.jpeg" class="myimage"/></div> */
    return res;
}

中序和后序遍历也是类似的，只要把 add(root.val) 放到中序和后序对应的位置就行了。

这个解法短小精干，但为什么不常见呢？

一个原因是这个算法的复杂度不好把控，比较依赖语言特性。

Java 的话无论 ArrayList 还是 LinkedList，addAll 方法的复杂度都是 O(N)，所以总体的最坏时间复杂度会达到 O(N^2)，除非你自己实现一个复杂度为 O(1) 的 addAll 方法，底层用链表的话是可以做到的，因为多条链表只要简单的指针操作就能连接起来。

当然，最主要的原因还是因为教科书上从来没有这么教过……

上文举了两个简单的例子，但还有不少二叉树的题目是可以同时使用两种思路来思考和求解的，这就要靠你自己多去练习和思考，不要仅仅满足于一种熟悉的解法思路。

综上，遇到一道二叉树的题目时的通用思考过程是：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。

3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。

我的刷题插件 更新了所有值得一做的二叉树题目思路，全部归类为上述两种思路，你如果按照插件提供的思路解法过一遍二叉树的所有题目，不仅可以完全掌握递归思维，而且可以更容易理解高级的算法：

后序位置的特殊之处

说后序位置之前，先简单说下中序和前序。

中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。

前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。

你可以发现，前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的：

这不奇怪，因为本文开头就说了前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻。

但这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

举具体的例子，现在给你一棵二叉树，我问你两个简单的问题：

1、如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？

2、如何打印出每个节点的左右子树各有多少节点？

第一个问题可以这样写代码：

java 🟢
// 二叉树遍历函数
void traverse(TreeNode root, int level) {
    if (root == null) {
        return;
    }
    // 前序位置
    printf("节点 %s 在第 %d 层", root, level);
    traverse(root.left, level + 1);
    traverse(root.right, level + 1);
}

// 这样调用
traverse(root, 1);

第二个问题可以这样写代码：

java 🟢
// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。

结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

接下来看下后序位置是如何在实际的题目中发挥作用的，简单聊下力扣第 543 题「二叉树的直径open in new window」，让你计算一棵二叉树的最长直径长度。

所谓二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点，比如下面这棵二叉树：

它的最长直径是 3，即 [4,2,1,3]，[4,2,1,9] 或者 [5,2,1,3] 这几条「直径」的长度。

解决这题的关键在于，每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。

现在让我求整棵树中的最长「直径」，那直截了当的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。

最大深度的算法我们刚才实现过了，上述思路就可以写出以下代码：

java 🟢
class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        // 对每个节点计算直径，求最大直径
        traverse(root);
        return maxDiameter;
    }

    // 遍历二叉树
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // 对每个节点计算直径
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        int myDiameter = leftMax + rightMax;
        // 更新全局最大直径
        maxDiameter = Math.max(maxDiameter, myDiameter);
        
        traverse(root.left);
        traverse(root.right);
    }

    // 计算二叉树的最大深度
    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        return 1 + Math.max(leftMax, rightMax);
    }
}

这个解法是正确的，但是运行时间很长，原因也很明显，traverse 遍历每个节点的时候还会调用递归函数 maxDepth，而 maxDepth 是要遍历子树的所有节点的，所以最坏时间复杂度是 O(N^2)。

这就出现了刚才探讨的情况，前序位置无法获取子树信息，所以只能让每个节点调用 maxDepth 函数去算子树的深度。

那如何优化？我们应该把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的。

所以，稍微改一下代码逻辑即可得到更好的解法：

java 🟢
class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        return 1 + Math.max(leftMax, rightMax);
    }
}

这下时间复杂度只有 maxDepth 函数的 O(N) 了。

讲到这里，照应一下前文：遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。

相关信息

思考题：请你思考一下，运用后序遍历的题目使用的是「遍历」的思路还是「分解问题」的思路？我会在文末给出答案。

反过来，如果你写出了类似一开始的那种递归套递归的解法，大概率也需要反思是不是可以通过后序遍历优化了。

我的刷题插件对于这类考察后序遍历的题目也有特殊的说明，并且会给出前置题目，帮助你由浅入深理解这类题目：

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

前文我说动态规划/回溯算法就是二叉树算法两种不同思路的表现形式，相信能看到这里的读者应该也认可了我这个观点。但有细心的读者经常问我：东哥，你的理解思路让我豁然开朗，但你好像一直没讲过 DFS 算法？

其实我在 一文秒杀所有岛屿题目 中就是用的 DFS 算法，但我确实没有单独用一篇文章讲 DFS 算法，因为 DFS 算法和回溯算法非常类似，只是在细节上有所区别。

这个细节上的差别是什么呢？其实就是「做选择」和「撤销选择」到底在 for 循环外面还是里面的区别，DFS 算法在外面，回溯算法在里面。

为什么有这个区别？还是要结合着二叉树理解。这一部分我就把回溯算法、DFS 算法、动态规划三种经典的算法思想，以及它们和二叉树算法的联系和区别，用一句话来说明：

动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：

  • 动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。
  • 回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
  • DFS 算法属于遍历的思路，它的关注点在单个「节点」。

怎么理解？我分别举三个例子你就懂了：

第一个例子，给你一棵二叉树，请你用分解问题的思路写一个 count 函数，计算这棵二叉树共有多少个节点。代码很简单，上文都写过了：

java 🟢
// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 我这个节点关心的是我的两个子树的节点总数分别是多少
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置，左右子树节点数加上自己就是整棵树的节点数
    return leftCount + rightCount + 1;
}

你看，这就是动态规划分解问题的思路，它的着眼点永远是结构相同的整个子问题，类比到二叉树上就是「子树」。

你再看看具体的动态规划问题，比如 动态规划框架套路详解 中举的斐波那契的例子，我们的关注点在一棵棵子树的返回值上：

java 🟢
int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

第二个例子，给你一棵二叉树，请你用遍历的思路写一个 traverse 函数，打印出遍历这棵二叉树的过程，你看下代码：

java 🟢
void traverse(TreeNode root) {
    if (root == null) return;
    printf("从节点 %s 进入节点 %s", root, root.left);
    traverse(root.left);
    printf("从节点 %s 回到节点 %s", root.left, root);

    printf("从节点 %s 进入节点 %s", root, root.right);
    traverse(root.right);
    printf("从节点 %s 回到节点 %s", root.right, root);
}

不难理解吧，好的，我们现在从二叉树进阶成多叉树，代码也是类似的：

java 🟢
// 多叉树节点
class Node {
    int val;
    Node[] children;
}

void traverse(Node root) {
    if (root == null) return;
    for (Node child : root.children) {
        printf("从节点 %s 进入节点 %s", root, child);
        traverse(child);
        printf("从节点 %s 回到节点 %s", child, root);
    }
}

这个多叉树的遍历框架就可以延伸出 回溯算法框架套路详解 中的回溯算法框架：

void backtrack(...) {
    for (int i = 0; i < ...; i++) {
        // 做选择
        ...

        // 进入下一层决策树
        backtrack(...);

        // 撤销刚才做的选择
        ...
    }
}

你看，这就是回溯算法遍历的思路，它的着眼点永远是在节点之间移动的过程，类比到二叉树上就是「树枝」。

你再看看具体的回溯算法问题，比如 回溯算法秒杀排列组合子集的九种题型 中讲到的全排列，我们的关注点在一条条树枝上：

// 回溯算法核心部分代码
void backtrack(int[] nums) {
    // 回溯算法框架
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        // 进入下一层回溯树
        backtrack(nums);

        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}

第三个例子，我给你一棵二叉树，请你写一个 traverse 函数，把这棵二叉树上的每个节点的值都加一。很简单吧，代码如下：

java 🟢
void traverse(TreeNode root) {
    if (root == null) return;
    // 遍历过的每个节点的值加一
    root.val++;
    traverse(root.left);
    traverse(root.right);
}

你看，这就是 DFS 算法遍历的思路，它的着眼点永远是在单一的节点上，类比到二叉树上就是处理每个「节点」。

你再看看具体的 DFS 算法问题，比如 一文秒杀所有岛屿题目 中讲的前几道题，我们的关注点是 grid 数组的每个格子（节点），我们要对遍历过的格子进行一些处理，所以我说是用 DFS 算法解决这几道题的：

// DFS 算法核心逻辑
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (grid[i][j] == 0) {
        return;
    }
    // 遍历过的每个格子标记为 0
    grid[i][j] = 0;
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

好，请你仔细品一下上面三个简单的例子，是不是像我说的：动态规划关注整棵「子树」，回溯算法关注节点间的「树枝」，DFS 算法关注单个「节点」。

有了这些铺垫，你就很容易理解为什么回溯算法和 DFS 算法代码中「做选择」和「撤销选择」的位置不同了，看下面两段代码：

java 🟢
// DFS 算法把「做选择」「撤销选择」的逻辑放在 for 循环外面
void dfs(Node root) {
    if (root == null) return;
    // 做选择
    print("我已经进入节点 %s 啦", root)
    for (Node child : root.children) {
        dfs(child);
    }
    // 撤销选择
    print("我将要离开节点 %s 啦", root)
}

// 回溯算法把「做选择」「撤销选择」的逻辑放在 for 循环里面
void backtrack(Node root) {
    if (root == null) return;
    for (Node child : root.children) {
        // 做选择
        print("我站在节点 %s 到节点 %s 的树枝上", root, child)
        backtrack(child);
        // 撤销选择
        print("我将要离开节点 %s 到节点 %s 的树枝上", child, root)
    }
}

看到了吧，你回溯算法必须把「做选择」和「撤销选择」的逻辑放在 for 循环里面，否则怎么拿到「树枝」的两个端点？

层序遍历

二叉树题型主要是用来培养递归思维的，而层序遍历属于迭代遍历，也比较简单，这里就过一下代码框架吧：

java 🟢
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    // 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 将下一层节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }
}

这里面 while 循环和 for 循环分管从上到下和从左到右的遍历：

后文 BFS 算法框架 就是从二叉树的层序遍历扩展出来的，常用于求无权图的最短路径问题。

当然这个框架还可以灵活修改，题目不需要记录层数（步数）时可以去掉上述框架中的 for 循环，比如后文 Dijkstra 算法 中计算加权图的最短路径问题，详细探讨了 BFS 算法的扩展。

值得一提的是，有些很明显需要用层序遍历技巧的二叉树的题目，也可以用递归遍历的方式去解决，而且技巧性会更强，非常考察你对前中后序的把控。

对于这类问题，我的刷题插件也会同时提供递归遍历和层序遍历的解法代码：

好了，本文已经够长了，围绕前中后序位置算是把二叉树题目里的各种套路给讲透了，真正能运用出来多少，就需要你亲自刷题实践和思考了。

希望大家能探索尽可能多的解法，只要参透二叉树这种基本数据结构的原理，那么就很容易在学习其他高级算法的道路上找到抓手，打通回路，形成闭环（手动狗头）。

最后，我在不断完善刷题插件对二叉树系列题目的支持，在公众号后台回复关键词「插件」即可下载，二叉树章节中的 递归专项练习 中会手把手带你运用本文所讲的技巧。

相关信息

思考题答案：文中后序遍历的例题使用了「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。

2022/5/12 更新：

关于层序遍历（以及其扩展出的 BFS 算法框架），我在最后多说几句。

如果你对二叉树足够熟悉，可以想到很多方式通过递归函数得到层序遍历结果，比如下面这种写法：

java 🟢
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    List<List<Integer>> levelTraverse(TreeNode root) {
        if (root == null) {
            return res;
        }
        // root 视为第 0 层
        traverse(root, 0);
        return res;
    }

    void traverse(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 前序位置，看看是否已经存储 depth 层的节点了
        if (res.size() <= depth) {
            // 第一次进入 depth 层
            res.add(new LinkedList<>());
        }
        // 前序位置，在 depth 层添加 root 节点的值
        res.get(depth).add(root.val);
        traverse(root.left, depth + 1);
        traverse(root.right, depth + 1);
    }
}

这种思路从结果上说确实可以得到层序遍历结果，但其本质还是二叉树的前序遍历，或者说 DFS 的思路，而不是层序遍历，或者说 BFS 的思路。因为这个解法是依赖前序遍历自顶向下、自左向右的顺序特点得到了正确的结果。

抽象点说，这个解法更像是从左到右的「列序遍历」，而不是自顶向下的「层序遍历」。所以对于计算最小距离的场景，这个解法完全等同于 DFS 算法，没有 BFS 算法的性能的优势。

还有优秀读者评论了这样一种递归进行层序遍历的思路：

java 🟢
class Solution {

    List<List<Integer>> res = new LinkedList<>();

    List<List<Integer>> levelTraverse(TreeNode root) {
        if (root == null) {
            return res;
        }
        List<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        traverse(nodes);
        return res;
    }

    void traverse(List<TreeNode> curLevelNodes) {
        // base case
        if (curLevelNodes.isEmpty()) {
            return;
        }
        // 前序位置，计算当前层的值和下一层的节点列表
        List<Integer> nodeValues = new LinkedList<>();
        List<TreeNode> nextLevelNodes = new LinkedList<>();
        for (TreeNode node : curLevelNodes) {
            nodeValues.add(node.val);
            if (node.left != null) {
                nextLevelNodes.add(node.left);
            }
            if (node.right != null) {
                nextLevelNodes.add(node.right);
            }
        }
        // 前序位置添加结果，可以得到自顶向下的层序遍历
        res.add(nodeValues);
        traverse(nextLevelNodes);
        // 后序位置添加结果，可以得到自底向上的层序遍历结果
        // res.add(nodeValues);
    }
}

这个 traverse 函数很像递归遍历单链表的函数，其实就是把二叉树的每一层抽象理解成单链表的一个节点进行遍历。

相较上一个递归解法，这个递归解法是自顶向下的「层序遍历」，更接近 BFS 的奥义，可以作为 BFS 算法的递归实现扩展一下思维。

引用本文的文章
Dijkstra 算法模板及应用 Git原理之最近公共祖先 【强化练习】二叉搜索树经典例题 I 【强化练习】二叉搜索树经典例题 II 【强化练习】利用后序位置解题 I 【强化练习】利用后序位置解题 II 【强化练习】利用后序位置解题 III 【强化练习】同时运用两种思维解题 【强化练习】用「分解问题」思维解题 I 【强化练习】用「分解问题」思维解题 II 【强化练习】用「遍历」思维解题 I 【强化练习】用「遍历」思维解题 II 【强化练习】用「遍历」思维解题 III 【强化练习】运用层序遍历解题 I 【强化练习】运用层序遍历解题 II 东哥带你刷二叉树（后序篇） 东哥带你刷二叉树（序列化篇） 东哥带你刷二叉树（思路篇） 东哥带你刷二叉树（构造篇） 前缀树算法模板秒杀五道算法题 动态规划和回溯算法的思维转换 后序遍历的妙用 回溯算法秒杀所有排列/组合/子集问题 回溯算法解题套路框架 图论基础及遍历算法 归并排序详解及应用 我的刷题心得：算法的本质 用栈模拟递归迭代遍历二叉树 算法学习和心流体验
引用本文的题目

安装 我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode力扣
100. Same Treeopen in new window100. 相同的树open in new window
1008. Construct Binary Search Tree from Preorder Traversalopen in new window1008. 前序遍历构造二叉搜索树open in new window
101. Symmetric Treeopen in new window101. 对称二叉树open in new window
1022. Sum of Root To Leaf Binary Numbersopen in new window1022. 从根到叶的二进制数之和open in new window
1026. Maximum Difference Between Node and Ancestoropen in new window1026. 节点与其祖先之间的最大差值open in new window
108. Convert Sorted Array to Binary Search Treeopen in new window108. 将有序数组转换为二叉搜索树open in new window
1080. Insufficient Nodes in Root to Leaf Pathsopen in new window1080. 根到叶路径上的不足节点open in new window
110. Balanced Binary Treeopen in new window110. 平衡二叉树open in new window
111. Minimum Depth of Binary Treeopen in new window111. 二叉树的最小深度open in new window
1110. Delete Nodes And Return Forestopen in new window1110. 删点成林open in new window
1120. Maximum Average Subtreeopen in new window🔒1120. 子树的最大平均值open in new window🔒
113. Path Sum IIopen in new window113. 路径总和 IIopen in new window
114. Flatten Binary Tree to Linked Listopen in new window114. 二叉树展开为链表open in new window
116. Populating Next Right Pointers in Each Nodeopen in new window116. 填充每个节点的下一个右侧节点指针open in new window
124. Binary Tree Maximum Path Sumopen in new window124. 二叉树中的最大路径和open in new window
1245. Tree Diameteropen in new window🔒1245. 树的直径open in new window🔒
1261. Find Elements in a Contaminated Binary Treeopen in new window1261. 在受污染的二叉树中查找元素open in new window
129. Sum Root to Leaf Numbersopen in new window129. 求根节点到叶节点数字之和open in new window
1315. Sum of Nodes with Even-Valued Grandparentopen in new window1315. 祖父节点值为偶数的节点和open in new window
1325. Delete Leaves With a Given Valueopen in new window1325. 删除给定值的叶子节点open in new window
1339. Maximum Product of Splitted Binary Treeopen in new window1339. 分裂二叉树的最大乘积open in new window
1367. Linked List in Binary Treeopen in new window1367. 二叉树中的链表open in new window
1372. Longest ZigZag Path in a Binary Treeopen in new window1372. 二叉树中的最长交错路径open in new window
1373. Maximum Sum BST in Binary Treeopen in new window1373. 二叉搜索子树的最大键值和open in new window
1376. Time Needed to Inform All Employeesopen in new window1376. 通知所有员工所需的时间open in new window
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Treeopen in new window1379. 找出克隆二叉树中的相同节点open in new window
1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Treeopen in new window🔒1430. 判断给定的序列是否是二叉树从根到叶的路径open in new window🔒
1443. Minimum Time to Collect All Apples in a Treeopen in new window1443. 收集树上所有苹果的最少时间open in new window
1448. Count Good Nodes in Binary Treeopen in new window1448. 统计二叉树中好节点的数目open in new window
145. Binary Tree Postorder Traversalopen in new window145. 二叉树的后序遍历open in new window
1457. Pseudo-Palindromic Paths in a Binary Treeopen in new window1457. 二叉树中的伪回文路径open in new window
1469. Find All The Lonely Nodesopen in new window🔒1469. 寻找所有的独生节点open in new window🔒
1485. Clone Binary Tree With Random Pointeropen in new window🔒1485. 克隆含随机指针的二叉树open in new window🔒
1490. Clone N-ary Treeopen in new window🔒1490. 克隆 N 叉树open in new window🔒
1593. Split a String Into the Max Number of Unique Substringsopen in new window1593. 拆分字符串使唯一子字符串的数目最大open in new window
1602. Find Nearest Right Node in Binary Treeopen in new window🔒1602. 找到二叉树中最近的右侧节点open in new window🔒
1612. Check If Two Expression Trees are Equivalentopen in new window🔒1612. 检查两棵二叉表达式树是否等价open in new window🔒
1740. Find Distance in a Binary Treeopen in new window🔒1740. 找到二叉树中的距离open in new window🔒
2049. Count Nodes With the Highest Scoreopen in new window2049. 统计最高分的节点数目open in new window
226. Invert Binary Treeopen in new window226. 翻转二叉树open in new window
250. Count Univalue Subtreesopen in new window🔒250. 统计同值子树open in new window🔒
254. Factor Combinationsopen in new window🔒254. 因子的组合open in new window🔒
257. Binary Tree Pathsopen in new window257. 二叉树的所有路径open in new window
267. Palindrome Permutation IIopen in new window🔒267. 回文排列 IIopen in new window🔒
270. Closest Binary Search Tree Valueopen in new window🔒270. 最接近的二叉搜索树值open in new window🔒
294. Flip Game IIopen in new window🔒294. 翻转游戏 IIopen in new window🔒
298. Binary Tree Longest Consecutive Sequenceopen in new window🔒298. 二叉树最长连续序列open in new window🔒
301. Remove Invalid Parenthesesopen in new window301. 删除无效的括号open in new window
332. Reconstruct Itineraryopen in new window332. 重新安排行程open in new window
333. Largest BST Subtreeopen in new window🔒333. 最大 BST 子树open in new window🔒
366. Find Leaves of Binary Treeopen in new window🔒366. 寻找二叉树的叶子节点open in new window🔒
386. Lexicographical Numbersopen in new window386. 字典序排数open in new window
404. Sum of Left Leavesopen in new window404. 左叶子之和open in new window
426. Convert Binary Search Tree to Sorted Doubly Linked Listopen in new window🔒426. 将二叉搜索树转化为排序的双向链表open in new window🔒
437. Path Sum IIIopen in new window437. 路径总和 IIIopen in new window
501. Find Mode in Binary Search Treeopen in new window501. 二叉搜索树中的众数open in new window
508. Most Frequent Subtree Sumopen in new window508. 出现次数最多的子树元素和open in new window
513. Find Bottom Left Tree Valueopen in new window513. 找树左下角的值open in new window
515. Find Largest Value in Each Tree Rowopen in new window515. 在每个树行中找最大值open in new window
530. Minimum Absolute Difference in BSTopen in new window530. 二叉搜索树的最小绝对差open in new window
538. Convert BST to Greater Treeopen in new window538. 把二叉搜索树转换为累加树open in new window
549. Binary Tree Longest Consecutive Sequence IIopen in new window🔒549. 二叉树中最长的连续序列open in new window🔒
559. Maximum Depth of N-ary Treeopen in new window559. N 叉树的最大深度open in new window
563. Binary Tree Tiltopen in new window563. 二叉树的坡度open in new window
572. Subtree of Another Treeopen in new window572. 另一棵树的子树open in new window
582. Kill Processopen in new window🔒582. 杀掉进程open in new window🔒
606. Construct String from Binary Treeopen in new window606. 根据二叉树创建字符串open in new window
617. Merge Two Binary Treesopen in new window617. 合并二叉树open in new window
623. Add One Row to Treeopen in new window623. 在二叉树中增加一行open in new window
654. Maximum Binary Treeopen in new window654. 最大二叉树open in new window
663. Equal Tree Partitionopen in new window🔒663. 均匀树划分open in new window🔒
666. Path Sum IVopen in new window🔒666. 路径总和 IVopen in new window🔒
669. Trim a Binary Search Treeopen in new window669. 修剪二叉搜索树open in new window
671. Second Minimum Node In a Binary Treeopen in new window671. 二叉树中第二小的节点open in new window
687. Longest Univalue Pathopen in new window687. 最长同值路径open in new window
776. Split BSTopen in new window🔒776. 拆分二叉搜索树open in new window🔒
865. Smallest Subtree with all the Deepest Nodesopen in new window865. 具有所有最深节点的最小子树open in new window
894. All Possible Full Binary Treesopen in new window894. 所有可能的真二叉树open in new window
897. Increasing Order Search Treeopen in new window897. 递增顺序搜索树open in new window
938. Range Sum of BSTopen in new window938. 二叉搜索树的范围和open in new window
951. Flip Equivalent Binary Treesopen in new window951. 翻转等价二叉树open in new window
965. Univalued Binary Treeopen in new window965. 单值二叉树open in new window
968. Binary Tree Camerasopen in new window968. 监控二叉树open in new window
971. Flip Binary Tree To Match Preorder Traversalopen in new window971. 翻转二叉树以匹配先序遍历open in new window
979. Distribute Coins in Binary Treeopen in new window979. 在二叉树中分配硬币open in new window
987. Vertical Order Traversal of a Binary Treeopen in new window987. 二叉树的垂序遍历open in new window
988. Smallest String Starting From Leafopen in new window988. 从叶结点开始的最小字符串open in new window
99. Recover Binary Search Treeopen in new window99. 恢复二叉搜索树open in new window
993. Cousins in Binary Treeopen in new window993. 二叉树的堂兄弟节点open in new window
998. Maximum Binary Tree IIopen in new window998. 最大二叉树 IIopen in new window
-剑指 Offer 06. 从尾到头打印链表open in new window
-剑指 Offer 26. 树的子结构open in new window
-剑指 Offer 27. 二叉树的镜像open in new window
-剑指 Offer 28. 对称的二叉树open in new window
-剑指 Offer 33. 二叉搜索树的后序遍历序列open in new window
-剑指 Offer 34. 二叉树中和为某一值的路径open in new window
-剑指 Offer 36. 二叉搜索树与双向链表open in new window
-剑指 Offer 55 - I. 二叉树的深度open in new window
-剑指 Offer 55 - II. 平衡二叉树open in new window
-剑指 Offer II 044. 二叉树每层的最大值open in new window
-剑指 Offer II 045. 二叉树最底层最左边的值open in new window
-剑指 Offer II 049. 从根节点到叶节点的路径数字之和open in new window
-剑指 Offer II 050. 向下的路径节点之和open in new window
-剑指 Offer II 051. 节点之和最大的路径open in new window
-剑指 Offer II 052. 展平二叉搜索树open in new window
-剑指 Offer II 054. 所有大于等于节点的值之和open in new window

《labuladong 的算法笔记》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

上次编辑于: