337. 打家劫舍 III

Problem: 337. 打家劫舍 III

思路

这次小偷在一颗树上打劫了。

我们使用递归来做,使用一个长度为2的数组，0表示：不偷当前房间得到的总金额，1表示：偷当前房间得到的总金额。

遍历顺序:

后序遍历,这样才可以先得到左右节点

递推公式:

//不偷cur，左右两边都可以偷或者不偷 取较大的
0: max(left[0], left[1]) + max(right[0], right[1])

//偷cur，那么就不能偷左右节点
1: cur->val + left[0] + right[0]

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        //不偷cur，取较大的偷 偷cur，那么就不能偷左右节点 
        return {max(left[0], left[1]) + max(right[0], right[1]), cur->val + left[0] + right[0]};
    }
};