十年網(wǎng)站開(kāi)發(fā)經(jīng)驗(yàn) + 多家企業(yè)客戶 + 靠譜的建站團(tuán)隊(duì)
量身定制 + 運(yùn)營(yíng)維護(hù)+專業(yè)推廣+無(wú)憂售后,網(wǎng)站問(wèn)題一站解決
小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口,我們稱之為 root 。
除了 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)查看詳情吧