解答
选择二叉树中不相邻的节点,使得节点之和为最大。
/// Memory Search
/// Time Complexity: O(n), where n is the nodes' number in the tree
/// Space Complexity: O(n)
class Solution {
public:
int rob(TreeNode* root) {
return rob(root, true);
}
private:
int rob(TreeNode* root, bool include){
if(root == NULL)
return 0;
int res = rob(root->left, true) + rob(root->right, true);
if(include)
res = max(root->val + rob(root->left, false) + rob(root->right, false),
res);
return res;
}
};
/// Redefine the recursive function and return a two-element array
/// represent the include and exclude maximum result for robbing the node
///
/// Time Complexity: O(n), where n is the nodes' number in the tree
/// Space Complexity: O(1)
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = tryRob(root);
return max(result[0], result[1]);
}
private:
vector<int> tryRob(TreeNode* root){
if(root == NULL)
return vector<int>(2, 0);
vector<int> resultL = tryRob(root->left);
vector<int> resultR = tryRob(root->right);
vector<int> res(2, 0);
res[0] = resultL[1] + resultR[1];
res[1] = max(res[0], root->val + resultL[0] + resultR[0]);
return res;
}
};
帖子还没人回复快来抢沙发