算法学习（7）：LeetCode刷题之二叉树递归

算法学习（7）：LeetCode刷题之二叉树递归 前言

二叉树天然具有递归的特性，所以刷二叉树基本都用递归的方式。建议先刷二叉树题目，因为很多经典的算法，比如分治、回溯、动态规划等，其实都是在处理树的问题。而树的问题，基本上离不开树的递归遍历框架，这篇文章通过二叉树的问题来理解递归。

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;
}

总结

刷二叉树的题目，关键是要弄清楚题目的要求，搞清楚根节点应该做什么，然后剩下的递归交给前/中/后序遍历模板就行了。