House Robber III

1class Solution {
2    public int rob(TreeNode root) {
3        int[] result = robDFS(root);
4        return Math.max(result[0], result[1]);
5    }
6
7    private int[] robDFS(TreeNode node) {
8        if (node == null) {
9            return new int[2];  // [0, 0]
10        }
11
12        int[] left = robDFS(node.left);
13        int[] right = robDFS(node.right);
14
15        int[] res = new int[2];
16        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
17        res[1] = node.val + left[0] + right[0];
18
19        return res;
20    }
21}