337.house-robber-iii 打家劫舍III

问题描述

337.打家劫舍III

解题思路

严格来说，这一题和198.打家劫舍，213.打家劫舍II的思路并不一致。

首先，这一道题遍历的是树，而不是一个数组。要比较的是选择目前节点和目前节点左子节点+右子节点，因此在遍历方式上需要采取后序遍历。

同时，作为二叉树的问题，一般是考虑递归进行处理：

• 递归的终止条件：
  • 当前节点为空；
• 递归函数的返回值：
  • 返回一个长度为2的数组dp，dp[0]表示不偷当前节点的最大金钱，dp[1]表示偷当前节点的最大金钱；
• 本级递归做什么：
  • 计算偷当前节点的收益val1，不偷当前节点的收益val2，返回{val2, val1}。

代码

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，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};