一:題目

二:上碼

/*** Definition for a binary tree node.* struct 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) {}* };*/ class Solution { public:/**思路:1.動態規劃YYDS2.分析題意:既然是二叉樹 那么和他離不開的就是遍歷順序 深度遍歷和廣度遍歷 我們可以知道的是本題和父節點有關的，那么我們就不考慮廣度遍歷;我們是考慮子節點的狀態來考慮我們是否偷取父節點;所以我們采用后序遍歷。3.用到遞歸1>:確定遞歸函數與參數我們采取兩個狀態來記錄我們是否偷取 0 表示不偷; 1 表示偷;vector<int> sumMoney(TreeNode* root)2>:確定遞歸的終止條件當我們遍歷到葉節點的時候 又往下遍歷了一次 那么我們的結點返回必定是不偷if(root == NULL) return {0,0}3>:確定遞歸的遞歸體vector<int> left = sumMoney(root->left);vector<int> right = sumMoney(root->right);那么我們的遞歸體就是為了表達當前結點偷與不偷;如果我們偷當前的結點;那么我們的當前已偷的總價值就是加上左右節不偷的價值int val1 = cur->val + left[0] + right[0];如果我們不偷當前的結點;那么我們現在的總價值就是就是左右結點中偷與不偷中價值的最大價值int val2 = max(left[0],left[1]]) + max(right[0],right[1])**/int rob(TreeNode* root) {vector<int> ans;ans = sumMoney(root);return max(ans[0],ans[1]);}vector<int> sumMoney(TreeNode* root) {if(root == NULL) return {0,0};vector<int> left = sumMoney(root->left);vector<int> right = sumMoney(root->right);int val1 = root->val + left[0] + right[0];//偷int val2 = max(left[0],left[1]) + max(right[0],right[1]);//不偷return {val2,val1};//注意這里的順序我們是 {不偷,偷} 因為我們的下標安排的是0 1 下標就是不偷與偷} };

天天向上 加油

總結

以上是生活随笔為你收集整理的leetcode337. 打家劫舍 III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。