BEATS 100.00% runtime and 99.54% memory!🔥🔥🔥 Intuitive and efficient solution! 😎🤑
IntuitionAt each node, we can either rob it or don't rob it.If we rob the node, we get node.val, but we can't rob the children of the node, but we can rob the c
![image.png](https://assets.leetcode.com/users/images/f9a6afbb-a9af-4daa-bf72-1e789e339c08_1741800973.5430012.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
At each node, we can either rob it or don't rob it.

If we rob the node, we get $node.val$, but we can't rob the children of the node, but we can rob the children of the children (since they are not direct connections) 😈.

If we don't rob the node, we can rob both of its children 😈!
# Approach
<!-- Describe your approach to solving the problem. -->
Using the intuition above, we take the max of both cases. But wait...🤔, the only recursive calls made are $rob(root.left)$ and $rob(root.right)$. That's because we store the value of $rob(node)$ in $node.val$ after we're done with that node, so we can get the value of, for example, $rob(node.left)$ by just getting $node.left.val$🔥. This makes our solution fast and memory efficient. Note: This is why we call $rob(root.left)$ and $rob(root.right)$ at the beginning.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n)$ since each node is visited once.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(1)$ since we don't use any auxillary collections.
# Code
```java []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        rob(root.left);
        rob(root.right);
        int robThisNode = root.val;
        int dontRobThisNode = 0;
        if (root.left != null) {
            dontRobThisNode += root.left.val;
            if (root.left.left != null) {
                robThisNode += root.left.left.val;
            }
            if (root.left.right != null) {
                robThisNode += root.left.right.val;
            }
        }
        if (root.right != null) {
            dontRobThisNode += root.right.val;
            if (root.right.left != null) {
                robThisNode += root.right.left.val;
            }
            if (root.right.right != null) {
                robThisNode += root.right.right.val;
            }
        }
        root.val = Math.max(robThisNode, dontRobThisNode);
        return root.val;
    }
}
```
['Java']