337. 打家劫舍 III

 class Solution {
    public int rob(TreeNode root) {
        int[] res=dfs(root);
        return Math.max(res[0],res[1]);
    }


    /**
     * int[] 存储当前结点偷不偷的获益情况
     * 0代表不偷，1代表偷
     *
     */
    private int[] dfs(TreeNode root) {
        //空结点返回偷的结果集均为0，啥也没有
        if (root==null){
            return new int[]{0,0};
        }

        //左孩子偷不偷获益情况
        int[] leftDfs=dfs(root.left);
        //右孩子偷不偷获益情况
        int[] rightDfs=dfs(root.right);

        int[] curr=new int[2];
        //当前结点不偷
        curr[0]=Math.max(leftDfs[0],leftDfs[1])+Math.max(rightDfs[0],rightDfs[1]);
        //当前结点偷
        curr[1]=leftDfs[0]+rightDfs[0]+root.val;

        return curr;
    }
}