手把手带你刷二叉树,第一期）

手持画笔二叉树(第一阶段)

https://labuladong.gitee.io/algo/2/18/21/

看完这篇文章，你不仅可以学习算法例程，还可以去LeetCode获取以下问题：

26.翻转二叉树(简单)

14.二叉树被扩展成链表(中)

16.填写每个节点的下一个右节点指针(中)

———

微信官方账号的著名著作《学习数据结构与算法框架思维》多次强调要先刷二叉树的题目，先刷二叉树的题目，先刷二叉树的题目，因为很多经典算法，以及我们前面讲过的所有回溯、移动回归、分治算法，其实都是树的问题，树的问题永远逃不出树的递归遍历框架的这些断行代码：

/*二叉树遍历框架*/

void traverse(TreeNode根){ 0

//序言遍历

导线(左根)

//有序遍历

导线(右根)

//后序遍历

}

微信官方账号的最后一篇文章让读者留言说对自己有什么问题还有疑问。接下来我可以专注写相关文章了。因此，很多读者说“递归”很难理解。说实话，递归解应该是最简单最容易理解的。流畅地编写递归代码是学好算法的基本功，而与二叉树相关的题目就是把递归基本功和框架思维练得最好。

我先花点时间解释一下二叉树算法的重要性。

一、二叉树的重要性

比如我们的经典算法“快速排序”和“合并排序”，你对这两种算法的理解是什么？如果你告诉我快速排序是二叉树的前序遍历，合并排序是二叉树的后序遍历，那么我知道你是算法高手。

为什么快速排序和合并排序与二叉树有关？让我们简单分析一下他们的算法思路和代码框架：

快速排序的逻辑是将nums[lo.嗨]，我们首先找到一个分界点P，交换元素使nums[lo.p-1]都小于或等于nums[p]，并且nums[p 1.hi]都大于nums[p]，然后递归转到nums[lo].p-1]。

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

void sort(int[] nums，int lo，int hi){ 0

/* * * * *前言遍历位置* * * * */

//通过交换元素构造分界点P

int p=分区(nums，lo，hi)；

/************************/

排序(nums、lo、p-1)；

sort(nums，p 1，hi)；

}

先构造分界点，再去左右子阵构造分界点。你认为这只是二叉树的前序遍历吗？

先说合并排序的逻辑。如果我们想分类.嗨]，我们首先对nums[lo]进行分类.mid]，然后排序nums[mid 1].hi]，最后合并这两个有序的子阵，整个数组就会被排序。

排序的代码框架如下：

void sort(int[] nums，int lo，int hi){ 0

int mid=(lo hi)/2；

排序(nums、lo、mid)；

排序(nums，mid 1，hi)；

/* * * * *后顺序遍历位置* * * * */

//合并两个排序的子数组。

合并(nums、lo、mid、hi)；

/************************/

}

先对左右子阵排序，然后合并(类似于合并有序链表的逻辑)。你认为这是二叉树的后序遍历框架吗？再说了，这就是传说中的各个击破算法，不过如此而已。

如果这些排序算法的细节你一目了然，还需要背这些算法代码吗？通过慢慢扩展框架很容易写出算法。

话虽如此，旨在说明二叉树算法应用广泛，甚至可以说只要涉及到递归，就可以抽象成二叉树问题，所以这篇文章和后续手把手给大家展示如何刷二叉树(第二阶段)和手把手刷二叉树(第三阶段)，我们有几节有趣的课直接讲，可以反映出递归算法的细微二叉树问题，东哥会教大家如何用算法框架来搞定。

二、写递归算法的秘诀

最近我们二叉树的共同祖先写道，写递归算法的关键是搞清楚函数的“定义”是什么，然后相信这个定义，用这个定义推导出最终的结果，永远不要跳入递归的细节。

怎么理解，我

们用一个具体的例子来说，比如说让你计算一棵二叉树共有几个节点：

// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // 自己加上子树的节点数就是整棵树的节点数
    return 1 + count(root.left) + count(root.right);
}

这个问题非常简单，大家应该都会写这段代码，root本身就是一个节点，加上左右子树的节点数就是以root为根的树的节点总数。

左右子树的节点数怎么算其实就是计算根为root.left和root.right两棵树的节点数呗，按照定义，递归调用count函数即可算出来。

写树相关的算法，简单说就是，先搞清楚当前root节点「该做什么」以及「什么时候做」，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

所谓「该做什么」就是让你想清楚写什么代码能够实现题目想要的效果，所谓「什么时候做」，就是让你思考这段代码到底应该写在前序、中序还是后序遍历的代码位置上。

我们接下来看几道算法题目实操一下。

三、算法实践

第一题、翻转二叉树

我们先从简单的题开始，看看力扣第 226 题「翻转二叉树」，输入一个二叉树根节点root，让你把整棵树镜像翻转，比如输入的二叉树如下：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

算法原地翻转二叉树，使得以root为根的树变成：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

通过观察，我们发现只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。

可以直接写出解法代码：

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }
    /**** 前序遍历位置 ****/
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

这道题目比较简单，关键思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。

值得一提的是，如果把交换左右子节点的代码复制粘贴到后序遍历的位置也是可以的，但是直接放到中序遍历的位置是不行的，请你想一想为什么这个应该不难想到，我会把答案置顶在公众号留言区。

首先讲这道题目是想告诉你，二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。

这种洞察力需要多刷题训练，我们看下一道题。

第二题、填充二叉树节点的右侧指针

这是力扣第 116 题，看下题目：

Node connect(Node root);

题目的意思就是把二叉树的每一层节点都用next指针连接起来：

而且题目说了，输入是一棵「完美二叉树」，形象地说整棵二叉树是一个正三角形，除了最右侧的节点next指针会指向null，其他节点的右侧一定有相邻的节点。

这道题怎么做呢把每一层的节点穿起来，是不是只要把每个节点的左右子节点都穿起来就行了

我们可以模仿上一道题，写出如下代码：

Node connect(Node root) {
    if (root == null || root.left == null) {
        return root;
    }
    root.left.next = root.right;
    connect(root.left);
    connect(root.right);
    return root;
}

这样其实有很大问题，再看看这张图：

节点 5 和节点 6 不属于同一个父节点，那么按照这段代码的逻辑，它俩就没办法被穿起来，这是不符合题意的。

回想刚才说的，二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：

// 主函数
Node connect(Node root) {
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
}
// 辅助函数
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** 前序遍历位置 ****/
    // 将传入的两个节点连接
    node1.next = node2;
    
    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

这样，connectTwoNode函数不断递归，可以无死角覆盖整棵二叉树，将所有相邻节点都连接起来，也就避免了我们之前出现的问题，这道题就解决了。

第三题、将二叉树展开为链表

这是力扣第 114 题，看下题目：

函数签名如下：

void flatten(TreeNode root);

我们尝试给出这个函数的定义：

给flatten函数输入一个节点root，那么以root为根的二叉树就会被拉平为一条链表。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表很简单，以下流程：

1、将root的左子树和右子树拉平。

2、将root的右子树接到左子树下方，然后将整个左子树作为右子树。

上面三步看起来最难的应该是第一步对吧，如何把root的左右子树拉平其实很简单，按照flatten函数的定义，对root的左右子树递归调用flatten函数即可：

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;
    
    flatten(root.left);
    flatten(root.right);
    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;
    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

你看，这就是递归的魅力，你说flatten函数是怎么把左右子树拉平的说不清楚，但是只要知道flatten的定义如此，相信这个定义，让root做它该做的事情，然后flatten函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

至此，这道题也解决了，我们旧文k个一组翻转链表的递归思路和本题也有一些类似。

四、最后总结

递归算法的关键要明确函数的定义，相信这个定义，而不要跳进递归细节。

写二叉树的算法题，都是基于递归框架的，我们先要搞清楚root节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。

二叉树题目的难点在于如何通过题目的要求思考出每一个节点需要做什么，这个只能通过多刷题进行练习了。

如果本文讲的三道题对你有一些启发，请三连，数据好的话东哥下次再来一波手把手刷题文，你会发现二叉树的题真的是越刷越顺手，欲罢不能，恨不得一口气把二叉树的题刷通。

接下来可阅读：

• 手把手刷二叉树（第二期）
• 手把手刷二叉树（第三期）

＿＿＿＿＿＿＿＿＿＿＿＿＿