打家劫舍(三)

1. 偷窃孩子节点房间的财物时，得到的最大收益steal；
2. 不偷窃孩子节点房间的财物时，得到的最大收益noSteal。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

class Info {
    public int steal;
    public int noSteal;
    public Info(int steal, int noSteal) {
        this.steal = steal;
        this.noSteal = noSteal;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int rob (TreeNode root) {
        // write code here
        Info info = process(root);
        return Math.max(info.steal, info.noSteal);
    }
    
    private Info process(TreeNode root) {
        if(root == null){
            return new Info(0, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        // 这一间偷，下面相邻的就不能偷
        int steal = root.val + leftInfo.noSteal + rightInfo.noSteal;
        // 这一间不偷，那下面相邻的可以偷可以不偷，选择收益大的方案
        int noSteal = Math.max(
            Math.max(leftInfo.steal + rightInfo.steal, 
                     leftInfo.noSteal + rightInfo.noSteal), 
            Math.max(leftInfo.steal + rightInfo.noSteal, 
                     leftInfo.noSteal + rightInfo.steal)
        );
        return new Info(steal, noSteal);
    }
}