vlambda博客
学习文章列表

设为“置顶或星标”，第一时间送达干货。

转自面向大象编程，作者nettee

本文将以两道题目为例，讨论如何拆解复杂的二叉树问题：

• LeetCode 1372. Longest ZigZag Path in a Binary Tree ^[1] 二叉树的最长“之字形”路径（Medium）
• LeetCode 1373. Maximum Sum BST in Binary Tree ^[2] 二叉树的最大 BST 子树和（Hard）

在前面的文章中，我们讲解了二叉树题目求解的基本方法：子问题方法，以及一些基本的技巧（、）。但是文章中的例子仅限于较简单的题目。如果你刚学会了这些基本方法就去做较难的题目，很容易抓瞎。本文教给你一种“三步走”的方法，即使面对复杂的二叉树问题也能抽丝剥茧，一步步得出解法！

我们要讲解的两道题目题号相连，均来自 LeetCode 第 21 场双周赛：

可以看到，两道题目是周赛里的后两道题，难度分别是 Medium 和 Hard。看起来有难度吧？没关系，跟上我的讲解，你也能做会这种难度的二叉树题目！

二叉树问题的「三步走」方法

大部分二叉树问题都可以用子问题方法求解。所谓子问题方法，就是在把求解的任务交给左右子树递归完成，最后在根结点处汇总所有的结果。

然而，在一些比较难的二叉树题目中，子问题并不是那么好梳理的。分析一个子问题的时候，可能又冒出了更多的子问题，这些子问题之间的关系也盘根错节…… 面对这种情况，其实我们需要一些解题的套路。这个套路，就是今天我要讲的二叉树问题 「三步走」方法。

「三步走」方法的三步分别为：

第一步【拆解子问题】：将问题尽可能地划分为子问题。 复杂问题的子问题很可能不止一个。要划分到不能再划分为止。这一步的目的是找出所有的子问题。

第二步【抽取全局变量】：如果题目所求的结果涉及到所有子树，考虑使用全局变量。 如果题目要返回的结果就是所有子树的最大值，或是所有子树的和，那么可以在遍历的过程中不断更新变量，让代码更简洁。

第三步【写出递归函数】：有几个子问题，递归函数就返回几个值。 很多问题恶心就恶心在这里，递归函数要返回好多个值，代码一团乱麻。但是如果你心里清楚每个返回值对应一个子问题，就不会那么混乱了。

下面，我们看看这两道例题如何使用三步走方法求解。

二叉树的最长之字形路径

题目描述：

给定一棵二叉树。二叉树的之字形路径是一条从上至下的路径，其中左向边（前往左子结点的边）和右向边（前往右子结点的边）交替出现。之字形路径的长度定义为路径中边的数量，或结点的数量减一。请返回给定二叉树中的最长之字形路径的长度。

下面我们直接套用三步走的解题套路：

第一步：拆解子问题

从题目示例中可以看出，二叉树的最长之字形路径不一定经过根结点。那么，我们首先想到的子问题划分方式是：

可以看到，子问题「最长之字形路径」是分给了子树求解，可是又出现了一个新的子问题「最长之字形根路径」（这里的根路径指的是从根结点出发的路径）。我们需要继续拆解这个子问题。

之字形根路径从根结点出发后，如果第一步向左，那么在左子树中下一步就要向右；如果第一步向右，那么在右子树中下一步就要向左。为了区分这两种情况，我们不妨把之字形路径分为左之路径（第一步向左的路径）和右之路径（第一步向右的路径），如下图所示。

这样，「最长之字形根路径」这个子问题可以拆解为：

这里需要注意的是，我们需要的左之路径和右之路径需要从根结点出发。这是因为，只有从根结点出发的路径，才能和父结点过来的路径连接起来。这样，我们又多了两个子问题：「最长左之根路径」和「最长右之根路径」。

另外，「最长之字形根路径」其实可以由「最长左之根路径」和「最长右之根路径」表示出来，上面的公式其实可以写成：

OK，这样我们就得到了完整的子问题递推公式。我们把所有的公式完整写下来：

在全面拆解子问题之后，我们就可以看出究竟存在几个子问题了。上面的公式中用颜色清晰标注了出来，共有三个子问题：

1. 最长之字形路径
2. 最长左之根路径
3. 最长右之根路径

第二步：抽取全局变量

我们拆解出的三个子问题是：(1) 「最长之字形路径」、(2) 「最长左之根路径」和 (3) 「最长右之根路径」。其中，第一个子问题就是题目要求的结果，我们叫它主要子问题，其他两个子问题是辅助求解，我们叫做辅助子问题。

在第二步中，我们要判断主要子问题是否要抽取成全局变量。在二叉树的遍历中抽取全局变量是一个很常见的技巧，我们在前一篇文章中专门讲了这个技巧。不了解该技巧的朋友，可以回顾前一篇文章：。

一般来说，要抽取为全局变量的子问题满足这样一个特点：题目要求的最终结果要么是所有子树上子问题的最大值，要么是所有子树上子问题的和，总之要涉及到所有子树上的子问题，而不仅仅是根结点上的子问题。

这道题就是一个典型的例子：我们要求出二叉树中最长的之字形路径，而这个路径又不一定经过根结点。于是，根结点要把任务交给左右子树计算，左右子树又要把任务交给自己的左右子树…… 最后计算出的结果，还要一层层地汇总上来。如果在递归函数的返回值里传递、汇总这些结果的话，代码会变得很啰嗦。而把这个结果放在一个全局变量里就会方便很多。

int res; // 全局变量：记录最长之字形路径的长度

public int longestZigZag(TreeNode root) {
    res = 0;
    traverse(root);
    return res;
}

void traverse(TreeNode root) {
	// ...
    // 直接更新全局变量的值
   	res = Math.max(res, ...);
}

第三步：写出递归函数

我们写递归函数的原则是：有几个子问题，递归函数就返回几个值。子问题我们一共拆解出了三个，其中一个抽取出来成了全局变量，那么我们的递归函数就需要返回两个值。

我们可以写出二叉树遍历代码的基本框架：

int res; // 全局变量：记录最长之字形路径的长度

public int longestZigZag(TreeNode root) {
    res = 0;
    traverse(root);
    return res;
}

// 返回两个值
// 返回值 0: 最长左之根路径的长度
// 返回值 1: 最长右之根路径的长度
int[] traverse(TreeNode root) {
	// ...
}

那么递归函数内部如何写呢？很简单，套用前面子问题的递推公式即可。

int res; // 全局变量：记录最长之字形路径的长度

public int longestZigZag(TreeNode root) {
    res = 0;
    traverse(root);
    return res - 1;
}

// 返回两个值
// 返回值 0: 最长左之根路径的长度
// 返回值 1: 最长右之根路径的长度
int[] traverse(TreeNode root) {
    // base case：空子树的左之、右之路径长度为 0
    if (root == null) {
        return new int[]{0, 0};
    }
    // 递归计算左右子树的子问题
    int[] left = traverse(root.left);
    int[] right = traverse(root.right);
    // 套用公式
    int leftzz = 1 + left[1];
    int rightzz = 1 + right[0];
    // 更新全局变量（主要子问题）
    res = Math.max(res, leftzz);
    res = Math.max(res, rightzz);
    // 返回值（两个辅助子问题）
    return new int[]{leftzz, rightzz};
}

Nice！一道复杂的题目就这样被我们一步步解决了。

二叉树的最大 BST 子树和

题目描述：

给定一棵普通二叉树，请找出其二叉搜索子树的最大结点值之和。

二叉搜索树（BST）定义为：

• 一个结点的左子树中的值都小于该结点的值；
• 一个结点的右子树中的值都大于该结点的值；
• 一个结点的左子树和右子树都是二叉搜索树。

看到题目难度标记为 Hard，是不是心里有点慌？没关系，我们继续套用三步走方法，庖丁解牛分解题目！

第一步：拆解子问题

这道题目描述起来稍微有点绕，我们先明确几个概念：

• 二叉搜索子树（BST 子树） 是一棵满足二叉搜索树性质的子树
• 一棵树的 结点和等于树中所有结点的值相加

我们要计算的是所有二叉搜索子树的结点之和的最大值。

仿照之前的套路，我们可以将子问题划分为：

那么如何判断当前二叉树是否是二叉搜索树呢？

这其中有设计到二叉树的最大值、最小值两个子问题，它们的递推公式为：

最后，我们还需要计算结点之和，二叉树的结点之和的递推公式为：

可以看到，这道题涉及到的子问题有点多，递推公式也很复杂，不愧是难度为 Hard 的题目。不过，不要被这么一大串公式吓到，我们拆解子问题的目的主要是为了数清楚子问题究竟有几个。而且我们现在把公式都写下来的话，等会儿写代码的时候就会轻松很多，直接照着这些公式翻译就可以了。

从上面拆解的子问题可以看出，这道题一共涉及到五个子问题：

1. BST 子树最大结点和
2. 二叉树的结点和
3. 是否是二叉搜索树
4. 二叉树的最小值
5. 二叉树的最大值

第二步：抽取全局变量

同样的方法，我们看看题目要求的最终结果：所有二叉搜索子树的结点之和的最大值。很显然，我们可以用全局变量保存这个值，每次找到一个二叉搜索子树，如果结点之和大于全局变量，就更新全局变量的值。这样，我们可以去掉第一个子问题「最大二叉搜索子树的结点之和」。

第三步：写出递归函数

五个子问题去掉一个之后，还剩四个子问题。那么，我们的递归函数就需要返回四个值。

不过这里我们遇到了一个新的问题：在四个子问题中，「是否是二叉搜索树」这个子问题返回的是 bool 类型，而其他子问题返回的是 int 类型。它们不方便放在一个数组里返回。不过没有关系，对于 Java 来说，没有什么问题是不能写一个类来解决的……

class TreeInfo {
    boolean isBST; // 子问题：是否是二叉搜索树
    int min; // 子问题：二叉树的最小值
    int max; // 子问题：二叉树的最大值
    int sum; // 子问题：二叉树的结点和
}

我们可以让递归函数返回一个 TreeInfo 对象，这样就可以打包返回四个值了。当然，对于 Python 选手来说，不用写类就可以直接返回四个值。

最终得到的题解代码如下：

// 用一个类包装递归函数的四个返回值
class TreeInfo {
    boolean isBST;
    int min;
    int max;
    int sum;

    TreeInfo(boolean isBST, int min, int max, int sum) {
        this.isBST = isBST;
        this.min = min;
        this.max = max;
        this.sum = sum;
    }
}

int maxSum; // 全局变量：记录二叉搜索子树的结点之和的最大值

public int maxSumBST(TreeNode root) {
    maxSum = 0;
    traverse(root);
    return maxSum;
}

TreeInfo traverse(TreeNode root) {
    // base case：空子树是二叉搜索树，最小值、最大值不存在，和为 0
    if (root == null) {
        return new TreeInfo(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
    }
    // 递归计算左右子树的子问题
    TreeInfo left = traverse(root.left);
    TreeInfo right = traverse(root.right);
    // 套用公式：计算结点之和
    int sum = root.val + left.sum + right.sum;
    // 套用公式：判断是否是二叉搜索树
    if (left.isBST && right.isBST && left.max < root.val && root.val < right.min) {
        // 当前子树是二叉搜索树的情况
        maxSum = Math.max(maxSum, sum);
        // 套用公式：计算二叉树最小值和最大值
        int min = Math.min(left.min, root.val);
        int max = Math.max(right.max, root.val);
        return new TreeInfo(true, min, max, sum);
    } else {
        // 当前子树不是二叉搜索树的情况
        return new TreeInfo(false, Integer.MAX_VALUE, Integer.MIN_VALUE, sum);
    }
}

总结

很多时候，拿到一个二叉树问题我们都能想到一点思路，但是最后为什么没做出来呢？因为怕太复杂，因为被各种条件和逻辑绕晕了。

本文的讲解是想让你了解一点：部分二叉树问题虽然复杂，但套路是固定的。你只要写出了所有子问题的递推关系，提取出全局变量，最后有几个子问题函数就返回几个值，这样就一定能写出一套正确的代码。这就像高考数学题一样，如果知识点你全都掌握了，只是计算量大一点，你会很怕它吗？

LeetCode 上的二叉树问题很多，如果想要系统练习和提高的话，可以找出所有带“二叉树”标签的题目，每道题都尝试划分子问题、写出递推关系。其实二叉树问题做多的就发现，就那么点套路。

参考资料