LeetCode Solutions
struct T {
int robRoot;
int notRobRoot;
};
class Solution {
public:
int rob(TreeNode* root) {
const auto& [robRoot, notRobRoot] = robOrNotRob(root);
return max(robRoot, notRobRoot);
}
private:
T robOrNotRob(TreeNode* root) {
if (root == nullptr)
return {0, 0};
const T l = robOrNotRob(root->left);
const T r = robOrNotRob(root->right);
return {root->val + l.notRobRoot + r.notRobRoot,
max(l.robRoot, l.notRobRoot) + max(r.robRoot, r.notRobRoot)};
}
};
|
class T {
public int robRoot;
public int notRobRoot;
public T(int robRoot, int notRobRoot) {
this.robRoot = robRoot;
this.notRobRoot = notRobRoot;
}
}
class Solution {
public int rob(TreeNode root) {
T t = robOrNotRob(root);
return Math.max(t.robRoot, t.notRobRoot);
}
private T robOrNotRob(TreeNode root) {
if (root == null)
return new T(0, 0);
T l = robOrNotRob(root.left);
T r = robOrNotRob(root.right);
return new T(root.val + l.notRobRoot + r.notRobRoot,
Math.max(l.robRoot, l.notRobRoot) + Math.max(r.robRoot, r.notRobRoot));
}
}
|
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def robOrNot(root: Optional[TreeNode]) -> tuple:
if not root:
return (0, 0)
robLeft, notRobLeft = robOrNot(root.left)
robRight, notRobRight = robOrNot(root.right)
return (root.val + notRobLeft + notRobRight,
max(robLeft, notRobLeft) + max(robRight, notRobRight))
return max(robOrNot(root))
|
