字节高频算法题，面试必考之递归算法解题套路。建议收藏！
本文介绍一种二叉树递归题目的思考和解题方法，配合题目，步步深入难题。
思考这类递归问题时，将注意力集中在本层节点要完成的任务以及要完成这个任务需要子节点提供什么数据（也就是递归函数的返回值）和父节点需要传递什么数据（也就是递归函数的参数）。
无需考虑子节点是怎么完成任务的，只需假设子节点已经完成了它的任务并能够提供关键数据给自己用（这点在后面的根据中序和前序遍历重构树以及树转链表题目尤为明显，根本不需要考虑子节点是怎么完成任务）。最后本层节点也将自己的处理结果返回给父节点以及传递子节点需要用到的参数。
下面用这个思路解决由易到难解决一些问题。
只需子节点返回信息给父节点
二叉树的高
LeetCode原题 leetcode-cn.com/problems/ma…
题目描述
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 复制代码
题解
题目所求是树的高，对于每个节点都有自己的高。而父节点的高是由本节点和兄弟节点的高决定的。
明确每层任务和如何驱动递归
对于每个节点来说，统计子树的高度，并计算本层的高度。并将这个高度信息返回给父节点。顺着树递归即可驱动递归。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务。
计算本子树的高度只需知晓左右子树的高度，求max再+1，因此需要子节点返回子树的高度信息。不需要父节点下发什么信息。
明确终止条件和最终题目所求
碰到节点为null的返回0即可，不需要判断节点是否为叶子，这样会过多判断语句。题目所求其实就是树根节点的高度。
AC代码
class Solution { public: int maxDepth(TreeNode* root) { if(root == nullptr) return 0; return std::max(maxDepth(root->left), maxDepth(root->right)) + 1; } }; 复制代码判断树是否为平衡二叉树
leetcode原题leetcode-cn.com/problems/ba…
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 复制代码
题解
由平衡二叉树的定义可知，每个节点都要满足平衡条件，也就是需要知晓其左右子树的高度信息。
明确每层任务和如何驱动递归
对于每个节点来说，统计子树的高度，并计算本层的高度。并将这个高度信息返回给父节点。顺着树递归即可驱动递归。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务
计算本子树的高度需知晓左右子树的高度，求max再+1，因此需要子节点返回子树的高度信息。由于可能某个子孙节点不满足平衡二叉树的定义，此时整颗树都不满足条件。为此还需要子孙节点返回是否满足平衡二叉树的定义信息。不需要父节点下发什么信息。
明确终止条件和最终题目所求
碰到节点为null的返回0即可，不需要判断节点是否为叶子。题目所求就是树的根节点是否满足平衡二叉树的条件。
AC代码
根据上面的分析，结合剪枝可以得出代码如下：
class Solution { public: bool isBalanced(TreeNode* root) { auto ret = dfs(root); return ret.second; } //由上面的分析可知，递归函数的返回值应该包括两个信息：1. 子树的高度；2. 子树是否满足平衡二叉树的条件。 std::pair<int, bool> dfs(TreeNode *root) { if(root == nullptr){ return std::make_pair(0, true); } auto left_ret = dfs(root->left); if(!left_ret.second){ return std::make_pair(0, false); } auto right_ret = dfs(root->right); if(!right_ret.second){ return std::make_pair(0, false); } if(std::abs(left_ret.first - right_ret.first) > 1){ return std::make_pair(0, false); } //+1是本层的节点 return std::make_pair(std::max(left_ret.first, right_ret.first)+1, true); } }; 复制代码验证二叉搜索树
leetcode原题leetcode-cn.com/problems/va…
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 复制代码
题解
这题目和验证树是否为平衡二叉树类似。由二叉搜索树定义可知，每个节点都需要满足二叉搜索的定义，也就是每个节点都需要知道左右子树的最大值和最小值。然后基于这个做判断。
明确每层任务和如何驱动递归
对于每个节点来说，获取左右子树的最大最小值，用本节点的值与左右子树的最值进行比较判断是否满足二叉搜索树的定义。最后返回本子树的最大最小值。并将这个高度信息返回给父节点。顺着树递归即可驱动递归。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务
判断本子树是否满足二叉搜索树的条件需知晓左右子树最大最小值，因此需要子节点返回子树的最值。由于可能某个子孙节点不满足二叉搜索树的定义，此时整颗树都不满足条件。为此还需要子孙节点返回是否满足二叉搜索树的定义信息。不需要父节点下发什么信息。
明确终止条件和最终题目所求
碰到叶子返回自身值并终止递归，其他情况继续递归。题目所求就是树的根节点是否满足搜索二叉树的条件
AC代码
class Solution { public: bool isValidBST(TreeNode* root) { if(root == nullptr) return true; auto tp = isValidBSTCore(root); return std::get<2>(tp); } //最小值，最大值，是否ok std::tuple<int, int, bool> isValidBSTCore(TreeNode *root) { if(root->left != nullptr && root->right != nullptr) { auto left_tp = isValidBSTCore(root->left); auto right_tp = isValidBSTCore(root->right); //子树出现问题 if(std::get<2>(left_tp) == false || std::get<2>(right_tp) == false) return std::make_tuple(0, 0, false); //左子树的最大值大于root 或者 右子树的最小值小于root if(std::get<1>(left_tp) >= root->val || std::get<0>(right_tp) <= root->val) return std::make_tuple(0, 0, false); else return std::make_tuple(std::get<0>(left_tp), std::get<1>(right_tp), true); } else if(root->left != nullptr) { auto left_tp = isValidBSTCore(root->left); if(std::get<2>(left_tp) == false || std::get<1>(left_tp) >= root->val) return std::make_tuple(0, 0, false); else return std::make_tuple(std::get<0>(left_tp), root->val, true); } else if(root->right != nullptr) { auto right_tp = isValidBSTCore(root->right); if(std::get<2>(right_tp) == false || std::get<0>(right_tp) <= root->val) return std::make_tuple(0, 0, false); else return std::make_tuple(root->val, std::get<1>(right_tp), true); } else { return std::make_tuple(root->val, root->val, true); } } }; 复制代码打家劫舍III
leetcode原题leetcode-cn.com/problems/ho…
题目描述
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 复制代码
例子
例一： 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 例二： 输入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. 复制代码
题解
对于一个节点而言，在不触发报警的情况下，可以偷取左右两个子节点，或者自身节点和两个孙子节点。但该节点是不能直接获取孙子节点的值，为此需要子节点返回该信息。
明确每层任务和如何驱动递归
根据左右子节点返回的值，选取最大的偷取方案。顺着树递归即可驱动递归。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务
需要返回左右子节点和孙子节点的值。因为子孙节点也是偷取的并且满足不报警原则，所以这里返回的子孙节点值不仅仅是子孙节点本身的值，而是偷取方案中包含了子节点，或者包含了孙节点的偷取方案的值。
明确终止条件和最终题目所求。
当碰到为null的节点时返回0即可终止递归。最终题目所求就是在树的根节点处做最优选取。
AC代码
class Solution { public: int rob(TreeNode* root) { auto ret = dfs(root); return std::max(ret.first, ret.second); } //first是包含root的最大值，second是不包含root的最大值 std::pair<int, int> dfs(TreeNode *root) { std::pair<int, int> ret = {0, 0}; if(root == nullptr) return ret; auto left = dfs(root->left); auto right = dfs(root->right); //包含root节点的值，就不能包含root的左右两个直接子树的值 ret.first = left.second + right.second + root->val; //不包含root节点的值, 则将root左右子树能达到的最大值加起来 ret.second = std::max(left.first, left.second) + std::max(right.first, right.second); return ret; } }; 复制代码父节点只下发信息(任务)给子节点
求根节点到叶子节点数字之和
leetcode原题leetcode-cn.com/problems/su…
题目描述
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字： 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 复制代码
例子
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026 复制代码
题解
明确每层任务和如何驱动递归
对于每个节点而言，累积从根节点数值传递到本层的计算结果。并传递给子节点。顺着树递归即可驱动递归。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务
本题目的方向是从根到叶子的，不需要子节点返回结果。但需要父节点下发它的累积结果。
明确终止条件和最终题目所求。
当碰到叶子节点时计算该叶子的累积值即可终止。最终题目所求是对所有叶子节点的值求和。最终叶子处的计算结果需要返回出去，但并不需要在递归函数中返回，只需保存在一个全局变量即可。
AC代码
class Solution { public: int sumNumbers(TreeNode* root) { m_sum = 0; dfs(root, 0); return m_sum; } void dfs(TreeNode *tr, int father_val){ if(tr == nullptr){ return ; } int cur_val = 10 * father_val + tr->val; if(tr->left == nullptr && tr->right == nullptr){ m_sum += cur_val; }else{ dfs(tr->left, cur_val); dfs(tr->right, cur_val); } } private: int m_sum; }; 复制代码父子节点间需要相互传递信息(任务)
根据前序和中序遍历结果重建二叉树
leetcode原题 leetcode-cn.com/problems/zh…
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 复制代码
例子
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 复制代码
题解
菩提本无树，如何像前面那样遍历树？ 虽然无树，但仍然可以递归遍历。将中序遍历的结果折半遍历，其实就是在遍历一颗二叉树。
由前序遍历和中序遍历的定义可知，前序遍历的第一个节点在中序遍历中，可以中序遍历结果分成左右两段。其中左边是该节点左子树，右边是该节点的右子树。也其实就是将右序遍历的结果二叉化也就是树化。
由了前面的分析，开始套路化。
明确每层任务和如何驱动递归
构造本层的树节点，并设置其左右子树。驱动递归的方式方法：由于是没有树可以直接递归的，因此本层的任务还需要根据前序节点值将中序数组划分成两段，并左右两段分别作为左右子树递归之。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务。
子节点返回其构造的子树根节点，让本层节点可以设置左右子树。父节点需要下发待遍历的前序和中序遍历数组。
明确终止条件和最终题目所求
当中序数组为空时，就说明没有数据构造子树了，也就是为null节点。此时可以终止递归。最终题目所求就是返回构造的第一个节点。
AC代码
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return dfs(preorder.begin(), preorder.end(), inorder.begin(), inorder.end()); } //用模板主要是因为不想敲那坨长长的iterator。当然完美转发也是一个原因。 template<typename T> TreeNode* dfs(T &&preStart, T preEnd, T inStart, T inEnd){ if(inStart == inEnd){ return nullptr; } auto pos = std::find(inStart, inEnd, *preStart); TreeNode *tr = new TreeNode(*pos); ++preStart; //这个已经被用掉了。 tr->left = dfs(std::forward<T>(preStart), preEnd, inStart, pos); tr->right = dfs(std::forward<T>(preStart), preEnd, std::next(pos), inEnd); return tr; } }; 复制代码如果对C++11的完美转发不熟悉，可以看下面版本
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { auto it = preorder.begin();//要用一个左值将preoder.begin()的右值固定下来，不然无法传递给dfs return dfs(it, preorder.end(), inorder.begin(), inorder.end()); } template<typename T> TreeNode* dfs(T &preStart, T preEnd, T inStart, T inEnd){ if(inStart == inEnd){ return nullptr; } auto pos = std::find(inStart, inEnd, *preStart); TreeNode *tr = new TreeNode(*pos); ++preStart; //这个已经被用掉了。 tr->left = dfs(preStart, preEnd, inStart, pos); tr->right = dfs(preStart, preEnd, std::next(pos), inEnd); return tr; } }; 复制代码上面代码时间复杂度是O(N^2)，如果想优化成O(N)可以先将中序遍历的结果和下标放到hash map中，然后将std::find改成哈希表查找即可。
最大二叉树
leetcode原题leetcode-cn.com/problems/ma…
题目描述
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下： 二叉树的根是数组 nums 中的最大元素。 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 返回有给定数组 nums 构建的 最大二叉树 。 复制代码
例子
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1] 解释：递归调用如下所示： - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。 - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。 - 空数组，无子节点。 - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。 - 空数组，无子节点。 - 只有一个元素，所以子节点是一个值为 1 的节点。 - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。 - 只有一个元素，所以子节点是一个值为 0 的节点。 - 空数组，无子节点。 复制代码
题解
这题和前面的根据前序和中序遍历结果构造二叉树是类似的，不展开了
AC代码
class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return dfs(nums.begin(), nums.end()); } template<typename T> TreeNode* dfs(T begin, T end) { if(begin == end) return nullptr; T it = std::max_element(begin, end); TreeNode *tr = new TreeNode(*it); tr->left = dfs(begin, it); tr->right = dfs(std::next(it), end); return tr; } }; 复制代码最大二叉树II
leetcode原题leetcode-cn.com/problems/ma…
题目描述
最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。 给出最大树的根节点 root。 就像之前的问题那样，给定的树是从列表 A（root = Construct(A)）递归地使用下述 Construct(A) 例程构造的： 如果 A 为空，返回 null 否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root root 的左子树将被构建为 Construct([A[0], A[1], ..., A[i-1]]) root 的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]]) 返回 root 请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A). 假设 B 是 A 的副本，并在末尾附加值 val。题目数据保证 B 中的值是不同的。 返回 Construct(B)。 复制代码
例子
输入：root = [4,1,3,null,null,2], val = 5 输出：[5,4,null,1,3,null,null,2] 解释：A = [1,4,2,3], B = [1,4,2,3,5] 复制代码
题解
题目要求是将待插入的值插入到一颗最大树中，使得插入后的树仍然是一颗最大树。也就是找一个合适的地方安放这个待插入的值。
明确每层任务和如何驱动递归
如果待插入的值大于本层的节点，那么说明需要创建一个新的节点取代本节点作为本节点的子节点，并且本节点应该作为新节点的子节点。如果待插入的值小于本层节点那么可以递归到左或者右子树。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务。
子节点返回处理后的子树根节点，让本层节点可以直接设置左右子树。 处理后的子树可以是插入待插入的值后的子树，也可以是源子树。
明确终止条件和最终题目所求
当遍历到叶子时，说明待插入的值比树中任意值都小，作为新的叶子即可。如果在中间层就完成了插入，那么直接返回终止递归。完成插入后，也就完成了题目所求。
AC代码
class Solution { public: TreeNode* insertIntoMaxTree(TreeNode* root, int val) { if(root == nullptr) return nullptr; return dfs(root, val); } TreeNode* dfs(TreeNode *root, int val) { if(root == nullptr) return new TreeNode(val); if(root->val < val) { TreeNode *tr = new TreeNode(val); tr->left = root; return tr; //返回插入后的新子树 } else { root->right = dfs(root->right, val); return root; //返回源子树 } } }; 复制代码将二叉树展开成双向链表
leetcode原题 leetcode-cn.com/problems/er…
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 复制代码
例子
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6] 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 复制代码
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 复制代码
题解一
这道题目是将搜索二叉树从树状打平成链表形式，并且链表中节点的顺序是中序遍历的顺序。这使得任意一个子树的节点在链表中都是相邻的。因此子树都需要将本子树打平成为一个链表。 对于一棵子树而言，打平后其是最终链表连续的一部分。为了将这段链表连接起来需要提供链表的头结点和尾节点。也是说，在递归的时候子节点需要向父节点返回打平后链表的头节点和尾节点。这样父节点才能将两段链表拼接起来。链表的头节点其实就是子树中的最左边节点，而尾节点则是子树的最右边节点。 因此子节点给父节点的返回信息是：该子节点最左边节点和最右边节点。
明确每层任务和如何驱动递归
驱动递归的方式是直接将左右子树递归之，得到左右两段链表。本层的节点刚好位于这两段链表的中间，将左右两段链表和本层节点拼接在一起即可。
明确需要子节点返回什么结果以及父节点需要下发什么信息才能完成本层的任务
子节点只需返回该段链表头节点和尾节点。父节点不需要下发信息。
明确终止条件和最终题目所求。
当碰到子树为空的终止即可。树的根节点返回的头尾节点就是题目所求。
AC代码一
有了上面的分析，很容易得出下面代码。
class Solution { public: Node* treeToDoublyList(Node* root) { if(root == nullptr) return nullptr; std::pair<Node*, Node*> p = dfs(root); p.second->right = p.first; p.first->left = p.second; return p.first; } std::pair<Node*, Node*> dfs(Node *tr){ Node *leftest = nullptr; Node *rightest = nullptr; if(tr->left == nullptr){ leftest = tr; }else{ //递归，让子树去完成它的任务。 std::pair<Node*, Node*> p = dfs(tr->left); //将左边这段链表和tr节点拼接在一起 leftest = p.first; p.second->right = tr; tr->left = p.second; } if(tr->right == nullptr){ rightest = tr; }else{ //递归，让子树去完成它的任务 std::pair<Node*, Node*> p = dfs(tr->right); //将右边这段链表和tr节点拼接在一起 rightest = p.second; p.first->left = tr; tr->right = p.first; } //返回本节点的结果 return std::make_pair(leftest, rightest); } }; 复制代码题解二
累了，不想写了。这里将当时刷题做的笔记原样抄录。这个笔记也是本文主要思路的来源。
对于某个节点tr，它应该放手(递归)左右子树去生成子链表。对于右子树需要其返回链表的第一个节点，此时tr->right指向返回的节点即可。对于左子树也要返回链表的首节点，因为tr节点需要拿这首节点向它的父节点交差。除了要求左右子树返回链表的首节点外，还要它们在链表尾部加上特定的节点。对于左子树，是加上tr；对于右子树则是tr父节点交代下来的一个节点。
AC代码二
class Solution { public: Node* treeToDoublyList(Node* root) { if(root == nullptr) return root; //因为最后得是一个环，所以最后插入一个临时节点。使得treeToDoublyListCore //返回后，能直接获取到最后一个节点 Node *tmp = new Node; Node *head = dfs(root, tmp); Node *last = tmp->left; last->right = head; head->left = last; return head; } Node* dfs(Node *tr, Node *rightNode) { if(tr->right == nullptr) { tr->right = rightNode; rightNode->left = tr; } else { Node *first = dfs(tr->right, rightNode); tr->right = first; first->left = tr; } return tr->left == nullptr ? tr : dfs(tr->left, tr); } };
作者：代码的色彩
链接：https://juejin.cn/post/7018181330596790285