vlambda博客
学习文章列表

手把手刷二叉树（训练递归思维）

刷算法题，一定先刷二叉树的题目。因为很多经典算法，以及所有回溯、动态规划、分治算法，其实都是树的问题。而树的问题就永远逃不开树的递归遍历框架这几行代码：

/* 二叉树遍历框架 */
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 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。接下来看几道算法题，实际操作一下。

三、算法实践

第一题 翻转二叉树 LeetCode 226 Easy

先从最简单的题开始。输入一个二叉树根节点 root ，让你把整棵树镜像翻转。

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

解法代码：

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

二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。这种洞察力只能多刷题训练。

第二题 填充二叉树节点的右侧指针 LeetCode 116 Medium

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 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;
}

上述代码不会将不属于同一父节点的节点连接起来，这不符合题意。

回想一下，二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，如果只依赖一个节点的话，肯定没办法找到跨父节点的两个相邻节点的。

既然一个节点做不到，那么我们就安排两个节点，将每一层二叉树节点连接起来可以细化成将每两个相邻节点都连接起来：

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

第三题 将二叉树展开为链表 LeetCode 114 Medium

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

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

void flatten(TreeNode root) {
    // base case
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    /* 后序遍历位置 */
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.left = null;
    root.right = left;
    TreeNode p  = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

这就是递归的魅力，你知道 flatten 函数时怎么把左右子树拉平的吗？说不清楚，但是你只要相信这个定义，让 root 做它该做的事情即可。

四、总结

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

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