二叉树天然具有递归的特性，所以刷二叉树基本都用递归的方式。建议先刷二叉树题目，因为很多经典的算法，比如分治、回溯、动态规划等，其实都是在处理树的问题。而树的问题，基本上离不开树的递归遍历框架，这篇文章通过二叉树的问题来理解递归。
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
那么，我们如何来写递归算法呢？写递归的关键在于要明确函数的定义是什么，然后相信这个定义，最后利用这个定义推导最终结果，切不可试图跳入递归中。
举个例子，我们来求一颗二叉树中共有几个节点：
// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
// base case
if (root == null) {
return 0;
}
// 自己加上子树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}
递归函数有固定的写法，首先函数要有出口，就是上面的base case，也就是问题的最小规模的处理方式，二叉树的最小规模是一颗空树null，其次函数要有递归，递归访问当前节点的左右子树，本题中root本身就是一个节点，加上左右子树的节点数就是以root为根的一棵树的节点总数。
左右子树的节点数怎么计算？就是计算以root.left和root.right两棵树的节点数，按照函数定义，递归调用count函数即可。由此可见，在写树相关的递归函数时，首先定义好函数的出口，然后搞清楚当前节点root该做什么，最后根据函数定义递归调用子节点，递归函数会让子节点做同样的事情。
正文 1、LeetCode No. 226 翻转二叉树我们观察到，只要把二叉树的每个节点的左右子节点进行交换，最后就能得到完全翻转后的二叉树。根据上面说的3步解法，可以很快写出题解：
// 将整棵树的节点翻转
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;
}
二叉树相关的题目一个难点就是，如何把题目的要求细化成每个节点要做的事情。
2、LeetCode No. 116 填充每个节点的下一个右侧节点指针题目规定了完美二叉树的定义：所有叶子节点都在同一层，且每个父节点都有两个子节点。二叉树的定义中增加了一个next指针，题目让填充每个节点的next指针，让这个指针指向下一个右侧的节点，如果找不到下一个右侧节点，则将next指针置为null。
这道题如果简单地将每个节点的左右子节点连起来其实是不够的，因为上图中节点5和6也是有连接的，但是他们不属于同一个父节点。于是我们需要一个辅助函数，来同时 *** 作2个节点。
// 主函数
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);
}
这道题目其实很适合用层序遍历来做，按时本文是讲递归的。
3、LeetCode No. 654 最大二叉树二叉树的题目有一类问题是构造型的，给你一个数组，按照规则构造出一颗二叉树。接下来的3道题目都是这个类型。
对于构造型的问题，则对于根节点来说，要做的就是将自己构造出来。
对于这道题目，输入的数组是【3，2，1，6，0，5】，对于整棵树的构造过程可以写成下面这种伪代码。
TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {
if (base case) return null;
// 找到数组中的最大值
TreeNode root = new TreeNode(6);
// 递归调用构造左右子树
root.left = constructMaximumBinaryTree([3,2,1]);
root.right = constructMaximumBinaryTree([0,5]);
return root;
}
也就是对于每一个节点的构造过程来说，要想办法在相应的区间里找到最大值，然后用分割后的区间去递归构造左右子树即可。
我们仍需要一个辅助函数，来控制nums数组的下标索引。
TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int lo, int hi) {
// base case
if (lo > hi) {
return null;
}
// 找到数组中的最大值和对应的索引
int index = -1, maxVal = Integer.MIN_VALUE;
for (int i = lo; i <= hi; i++) {
if (maxVal < nums[i]) {
index = i;
maxVal = nums[i];
}
}
TreeNode root = new TreeNode(maxVal);
// 递归调用构造左右子树
root.left = build(nums, lo, index - 1);
root.right = build(nums, index + 1, hi);
return root;
}
4、LeetCode No. 105 从前序和中序遍历序列构造二叉树
上大学时学习数据结构二叉树时，期末考试就有一个题目要根据前序和中序，或者后序和中序遍历序列，还原一个二叉树。现在让写代码实现这个过程。
类似上一个题目，我们需要确定好根节点的值，把根节点构造出来，然后递归构造左右子树。
我们再来回顾以下学习大学时这个还原的过程是什么样的。找到根节点很简单，前序遍历序列的第一个值preorder[0]就是根节点的值，然后在中序遍历序列中找到根节点的值，以它为界，左边的元素都在左子树，右边的元素都在右子树。
我们同样需要一个辅助函数，入参是下标，来分割数组，对于下面的代码，我们重点是要确定在递归构造左右子树时，怎么分割数组，即方法中的 ？处怎么填。
TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(preorder, ?, ?,
inorder, ?, ?);
root.right = build(preorder, ?, ?,
inorder, ?, ?);
return root;
}
对于中序遍历序列，找到了root的index位置，也就比较好确认左右子数组的起始位置了。对于前序遍历来说，我们还需要知道一个信息，即左子树节点的个数leftSize，才能知道左右子树的起始位置。
根据上面的图示，补充缺失的代码如下：
int leftSize = index - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
辅助函数的完整代码如下：
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
// 先构造出当前根节点
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
5、LeetCode No. 106 从中序和后续遍历序列构造二叉树
跟上一题解法是一致的，先找到根节点，把根节点构造出来，再递归构造左右子树。
我们仍然需要确定左右子树区间的起始位置。
完整代码如下：
TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd) {
return null;
}
// root 节点对应的值就是后序遍历数组的最后一个元素
int rootVal = postorder[postEnd];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
// 左子树的节点个数
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(inorder, inStart, index - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = build(inorder, index + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
return root;
}
总结
刷二叉树的题目，关键是要弄清楚题目的要求，搞清楚根节点应该做什么，然后剩下的递归交给前/中/后序遍历模板就行了。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）