Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
3 / \ 2 3 \ \ 3 1Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3 / \ 4 5 / \ \ 1 3 1Maximum amount of money the thief can rob = 4 + 5 = 9.
A:
首先:就是遍历一遍。然后考虑2种情况。 取或者不取 node。
要防止多次(重复)遍历。 有个简单的方法,就是用hash. 这里,我们用hashMap来保存结果
/** * 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) { if(not root) return 0; if(M.find(root) != M.end()) return M[root]; int withRoot = root->val + (root->left? rob(root->left->left) + rob(root->left->right) :0 )+ \ (root->right ? rob(root->right->left) + rob(root->right->right) : 0); int noRoot = rob(root->left) + rob(root->right); M[root] = max(withRoot, noRoot); return M[root]; } private: unordered_map<TreeNode*, int> M; };
Mistakes:
1: withRoot 计算的时候, 三目运算符, 要括起来。
No comments:
Post a Comment