题解 | 打家劫舍III

题干解析

去除背景后： 题设定义一颗二叉树，允许我们任意选取不连续的节点，要求返回所有选取方式中所选取节点值之和最大的值。

算法思路

递归分解问题：

• 针对空树根，我们无从选择。
• 针对单节点树根，我们有两种选择：选择该根节点/不选择该根节点。
• 针对一般树根，依旧两种选择：选择该根节点/不选择该根节点。

我们想要让我们的选择总和尽可能大。考虑普通的树根：

• 如果我们选择根节点，则两个子树需在根节点均不能选的情况下得到最大选择。
• 如果我们不选择根节点，则子树的节点选择并无过多限制，得到最大选择了即可。

子树的最大选择也可以依照树根类推，只不过同样考虑两种情况，选择子树根节点/不选择子树根节点。

以此作为递归元问题即可解决该问题。

实现代码

class L337 {
    pair<int, int> dfs(TreeNode *node) {
        if (!node) return {0, 0}; // 空树
        auto [leftR, leftNR] = dfs(node->left); // 左子树的两种最大选择情况
        auto [rightR, rightNR] = dfs(node->right); // 右子树
        int R = leftNR + rightNR + node->val; // 选择根节点
        int NR = max(leftR, leftNR) + max(rightR, rightNR); // 不选择根节点
        return {R, NR};
    }
public:
    int rob(TreeNode* root) {
        auto [rootR, rootNR] = dfs(root);
        return max(rootR, rootNR);
    }
};

复杂度分析

• 时间复杂度：每个节点递归访问一次，时间复杂度为。
• 空间复杂度：最坏情况下，二叉树是一个链表，递归空间消耗占主体，空间复杂度最坏为。