The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

&nbsp;
Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.


Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 104].
	0 &lt;= Node.val &lt;= 104


class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        hashMap = {}
        
        def helper(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            if root in hashMap:
                return hashMap[root]
            ansOption1 = root.val
            if root.left is not None:
                ansOption1 += (helper(root.left.left) + helper(root.left.right))
            if root.right is not None:
                ansOption1 += (helper(root.right.left) + helper(root.right.right))
            ansOption2 = helper(root.left) + helper(root.right)
            ansFinal = max(ansOption1, ansOption2)
            hashMap[root] = ansFinal
            return ansFinal
        
        return helper(root)
                
/**
 * 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 {
    static class Pair{
        int withRob=0;
        int withoutRob=0;
    } 
    public int rob(TreeNode root) {
        Pair nodeRob=rob_(root);
        
        return Math.max(nodeRob.withRob,nodeRob.withoutRob);
    }
    
    public Pair rob_(TreeNode root){
        if(root==null){
            return new Pair();
        }
        
        Pair l=rob_(root.left);
        Pair r=rob_(root.right);
        
        Pair nodeRob=new Pair();
        nodeRob.withRob=root.val+l.withoutRob+r.withoutRob;
                nodeRob.withoutRob=Math.max(l.withRob,l.withoutRob)+Math.max(r.withRob,r.withoutRob);
        return nodeRob;
    }
}
class Solution {
public:
    vector<int> dp(TreeNode* root)
    {
        vector<int> ans(2,0); //dp[0]: maximal money you can get by robbing current node. dp[1]: maximal money you can get when not rob this node
        if(root==NULL) return ans;
        vector<int> left=dp(root->left);
        vector<int> right=dp(root->right);
        ans[0]=root->val+left[1]+right[1];
        ans[1]=max(left[0],left[1])+max(right[0],right[1]);
        return ans;
    }
    int rob(TreeNode* root) {
        vector<int> ans=dp(root);
        return max(ans[0],ans[1]);
    }
};
var rob = function(root) {
    const dfs = (node = root) => {
        if (!node || node.val === null) return [0, 0];
        const { val, left, right } = node;
        const [robL, notRobL] = dfs(left);
        const [robR, notRobR] = dfs(right);
        const rob = val + notRobL + notRobR;
        const notRob = Math.max(robL, notRobL) + Math.max(robR, notRobR);

        return [rob, notRob];
    };

    return Math.max(...dfs());
};
House Robber III