这是我参与更文挑战的第 14 天，活动详情查看：更文挑战

树型 DP

树型 DP，顾名思义，这一类题目会在一棵二叉树，或者多叉树上进行 DP。虽然看起来是一个二叉树问题，但本质上需要用到 DP 的知识才能求解。

例子：二叉树抢劫

题目

在上次打劫完一条街道之后和一圈房屋后，小偷又发现一个新的可行窃的地区。这个地区只有一个入口，我们称为“根”。除了“根”之外，每栋房子有且只有一个“父”房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

输入：[3,2,3,null,3,null,1]

输出：7

解释：小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

分析

我们看到“最高”两字，应该可以想到使用 DP 方法来试一试。首先还是使出我们的绝招，最后一步。

1. 最后一步

假设小偷在抢劫的时候，总是先抢树的子树，那么最后一步肯定就是二叉树的根结点。根结点只有两种可能：

抢根结点
不抢根结点

得到这两种可能之后，我们只需要在这两种情况中取最大值就可以了。

2. 子问题

如果我们进一步展开根结点的 2 种情况，可以发现：

抢根结点，此时不能抢左右两棵子树的根结点；

不抢根结点，此时可以抢左右两棵子树的根结点，也可以不抢两棵子树的根结点。

我们发现，根结点需要得到两个信息：<抢 root 的最大收益,不抢 root 的最大收益>，并且左右子树也是需要这两个信息。

那么我们可以定义一个函数 f(x)，来描述最后一步的需求，以及子问题的需求：

f(x) = <抢 x 的最大收益, 不抢 x 的最大收益>

为了后面描述的方便，我们会用到以下缩写表示上述两个维度的信息：

f(x) = <抢,不抢> = <抢 x 的最大收益, 不抢 x 的最大收益>
max(f(x)) = max<f(x).抢,f(x).不抢>

3. 递推关系

到这里，我们可以根据最后一步和子问题写出递推关系：

f(root).抢 = root.val + f(root.left).不抢 + f(root.right).不抢
f(root).不抢 = max(f(root.left)) + max(f(root.right)))

4. f(x) 的表示

首先我们看一下 f(x) 的返回值，由于返回值只有两个。这比较好处理，对于 Python 来说，可以直接返回两个值，而对于 Java 来说，可以直接返回 long[2] 数组。

然后再看一下 f(x) 的表示。我们从底层开始往上抢的时候，应该只有相邻的两层才会有相互的依赖。

相隔更远的层间信息不需要保留，所以 f(x) 函数并不需要一个哈希或者数组来记录 [x] 的信息。相当于直接使用 DFS，而不需要记忆化 DFS。

5. 初始条件与边界

当遇到一棵空树的时候，只需要返回 long[2] = {0, 0} 就可以了，也就是收益为 0。

6. 计算顺序

这里我们采用的是先抢树的子树，因此，顺序上需要使用后序遍历。

完整代码

到这里，我们已经可以写出如下代码了（解析在注释里）：

class Solution {
    // 返回值是一个pair
    // ans[0]表示抢当前根结点
    // ans[1]表示不能抢当前结点
    private long[] postOrder(TreeNode root) {
        if (root == null) {
            return new long[] { 0, 0 };
        }
        long[] l = postOrder(root.left);
        long[] r = postOrder(root.right);
        // 如果要抢当前结点
        long get = root.val;
        // 那么两个子结点必然不能抢
        get += l[1] + r[1];
        // 如果不抢当前结点
        long skip = 0;
        // 那么两个子结点可以抢，也可以不抢
        skip += Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new long[] { get, skip };
    }
    public int rob(TreeNode root) {
        long[] ans = postOrder(root);
        return (int) Math.max(ans[0], ans[1]);
    }
}
复制代码