House Robber III (上圖我該點那個呢？)

04-27

好久沒有更新了，因為最近一直在折騰新系統---Ubuntu，最近暫時一段時間想放棄Windows。

廢話不多說，今天給大家分享的是House Robber III，其中House Robber 1 和 2已經在我的上一篇文章說過，現在我們是時候進擊3了。不過所不同的是，3已經不在是動態規劃問題了，而是與樹結構相關。

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1

3 / 2 3 3 1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

3 / 4 5 / 1 3 1

Maximum amount of money the thief can rob = 4 + 5 = 9.

用一張圖來阻斷你們看答案

與樹相關的問題基本都是採用遞歸調用來解決，當然你可能分不清遞歸調用和迭代的關係，我恰好看到一張圖很好的說明了這個問題。

遞歸 :

迭代：

參考程序

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int rob(TreeNode* root) { pair<int,int> result = rob_helper(root); return max(result.first, result.second); }private: pair<int,int> rob_helper(TreeNode * root) { if(!root) return pair<int,int>(0,0); pair<int, int> status_left = rob_helper(root->left); pair<int, int> status_right = rob_helper(root->right); int rob = status_left.second + status_right.second + root->val; int not_rob = max(status_left.first, status_left.second) + max(status_right.first, status_right.second); return pair<int,int>(rob,not_rob); } int max(int a, int b) { return a>b?a:b; }};

歡迎評論和點贊，也歡迎關注個人微信公眾號liss_H。