337. 打家劫舍 III -JZTXT

方法：树形dp

解题思路

对于每个节点，可能有选或者不选两种情况，对于两种情况下的数值均进行返回，其可以有子节点的数值转移而来；
假设第一个返回值表示选当前节点的值 \(select\)，第二个表示不选的值 \(no_select\)，先计算其子节点的返回值，\(left\) 和 \(rigth\)；
select = val + left.second + right.second，表示选择当前节点，则子节点就不能选择；
no_select = max(left.first, left.second) + max(right.first, right.second)，表示不选择当前节点，那么子节点可选可不选，此时根据题意选择最大或最小值进行计算；
递归边界：当指针为空时，返回 \(\{0, 0\}\)。

代码

class Solution {
public:
    int rob(TreeNode* root) {
        function<pair<int, int>(TreeNode*)> dfs = [&](TreeNode* root) -> pair<int, int> {
            if (!root) return {0, 0};
            pair<int, int> left, right; // first 表示选，second 表示不选
            left = dfs(root->left);
            right = dfs(root->right);
            int rob = root->val + left.second + right.second;
            int not_rob = max(left.first, left.second) + max(right.first, right.second);
            return {rob, not_rob};
        };
        pair<int, int> ans = dfs(root);
        return max(ans.first, ans.second);
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。