关于算法:东哥手把手带你刷二叉树第一期

读完本文，你能够去力扣拿下如下题目：

226. 翻转二叉树

114. 二叉树开展为链表

116. 填充每个节点的下一个右侧节点指针

———–

咱们的成名之作 学习数据结构和算法的框架思维 中屡次强调，先刷二叉树的题目，先刷二叉树的题目，先刷二叉树的题目，因为很多经典算法，以及咱们前文讲过的所有回溯、动归、分治算法，其实都是树的问题，而树的问题就永远逃不开树的递归遍历框架这几行破代码：

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

上篇公众号文章让读者留言说说对什么问题还有纳闷，我接下来能够重点写一写相干的文章。后果还有很多读者说感觉「递归」十分难以了解，说实话，递归解法应该是最简略，最容易了解的才对，行云流水地写递归代码是学好算法的基本功，而二叉树相干的题目就是最练习递归基本功，最练习框架思维的。

我先花一些篇幅阐明二叉树算法的重要性。

一、二叉树的重要性

举个例子，比如说咱们的经典算法「疾速排序」和「归并排序」，对于这两个算法，你有什么了解？ 如果你通知我，疾速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后续遍历，那么我就晓得你是个算法高手了 。

为什么疾速排序和归并排序能和二叉树扯上关系？咱们来简略剖析一下他们的算法思维和代码框架：

疾速排序的逻辑是，若要对 nums[lo..hi] 进行排序，咱们先找一个分界点 p，通过替换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，而后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最初整个数组就被排序了。

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

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] 排序，最初把这两个有序的子数组合并，整个数组就排好序了。

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

void sort(int[] nums, int lo, int hi) {int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历地位 ******/
    // 合并两个排好序的子数组
    merge(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 节点它本人要做什么，而后依据题目要求抉择应用前序，中序，后续的递归框架。

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

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