[力扣c++实现]337.打家劫舍III-创新互联

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

成都创新互联公司是专业的三原网站建设公司，三原接单;提供成都做网站、成都网站建设、成都外贸网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行三原网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 [1, 104] 范围内
0<= Node.val<= 104

#include#include 
#includestruct TreeNode {int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

typedef struct TreeNode Node;

class Solution {public:
    int robNode(TreeNode* node)
    {if (!node) return 0;
        int val1 = 0;
        if (nodesMaxValue.count(node)) return nodesMaxValue[node];
        if (node->left)
        {val1 += robNode(node->left->left);
            val1 += robNode(node->left->right);
        }

        if (node->right)
        {val1 += robNode(node->right->left);
            val1 += robNode(node->right->right);
        }

        val1 += node->val;

        int val2 = 0;
        val2 += robNode(node->left);
        val2 += robNode(node->right);

        nodesMaxValue[node] = std::max(val1,val2);
        return nodesMaxValue[node];
    }

    int rob(TreeNode* root) {return robNode(root);
    }

private:
    std::unordered_mapnodesMaxValue;
};

int main()
{Solution slu;
    Node root(3);
    Node node1(2);
    Node node2(3);
    Node node3(3);
    Node node4(1);
 
    root.left = &node1;
    root.right= &node2;
    node1.right = &node3;
    node2.right = &node4;
    
    std::cout<< slu.rob(&root)<< std::endl;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：[力扣c++实现]337.打家劫舍III-创新互联
本文URL：http://mswzjz.cn/article/hpsgj.html