[力扣c++實(shí)現(xiàn)]337.打家劫舍III-創(chuàng)新互聯(lián)

337. 打家劫舍 III

小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為 root 。

成都創(chuàng)新互聯(lián)公司是專業(yè)的三原網(wǎng)站建設(shè)公司，三原接單;提供成都做網(wǎng)站、成都網(wǎng)站建設(shè)、成都外貿(mào)網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行三原網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

除了 root 之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹(shù)”。 如果 兩個(gè)直接相連的房子在同一天晚上被打劫 ，房屋將自動(dòng)報(bào)警。

給定二叉樹(shù)的 root 。返回 在不觸動(dòng)警報(bào)的情況下 ，小偷能夠盜取的最高金額 。

示例 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

提示：

樹(shù)的節(jié)點(diǎn)數(shù)在 [1, 104] 范圍內(nèi)
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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：[力扣c++實(shí)現(xiàn)]337.打家劫舍III-創(chuàng)新互聯(lián)
文章路徑：http://m.jiaotiyi.com/article/hpsgj.html