/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int Rob(TreeNode root)
        {
            int[] num = dfs(root);
            return Math.Max(num[0], num[1]);
        }

        private int[] dfs(TreeNode x)
        {
            if (x == null) return new int[2];
            int[] left = dfs(x.left);
            int[] right = dfs(x.right);
            int[] res = new int[2];
            res[0] = left[1] + right[1] + x.val;
            res[1] = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
            return res;
        }
}