The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "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 forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

3

    / \
   2   3
    \   \ 

3   1

Maximum amount of money the thief can rob =

3

+

3

+

1

=

7

.

Example 2:

     3
    / \

4
5

  / \   \ 
 1   3   1

Maximum amount of money the thief can rob =

4

+

5

=

9

.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private class Node{
        int rob;
        int not_rob;

        public Node(int rob, int not_rob){
            this.rob = rob;
            this.not_rob = not_rob;
        }
    }

    public int rob(TreeNode root) {
        if (root == null) return 0;

        Node result = helper(root);

        return Math.max(result.rob, result.not_rob);
    }

    private Node helper(TreeNode root){
        if (root == null){
            return new Node(0, 0);
        }

        Node left = helper(root.left);
        Node right = helper(root.right);

        int rob_cur = root.val + left.not_rob + right.not_rob;
        int not_rob_cur = Math.max(left.rob, left.not_rob) + Math.max(right.rob, right.not_rob);

        return new Node(rob_cur, not_rob_cur);
    }
}