• 欢迎光临~

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

开发技术 开发技术 2022-10-14 次浏览

问题描述

337.打家劫舍III

解题思路

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

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

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

  • 递归的终止条件:
    • 当前节点为空;
  • 递归函数的返回值:
    • 返回一个长度为2的数组dpdp[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};
    }
};
程序员灯塔
转载请注明原文链接:337.house-robber-iii 打家劫舍III
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com