• Time:O(n)
• Space:O(n)

## C++

``````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)
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)};
}
};
``````

## JAVA

``````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));
}
}
``````

## Python

``````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))
``````