House Robber III 535

Question

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

3 / \ 2 3 \ \ 3 1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

3

/ \ 4 5 / \ \ 1 3 1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Solution

这题和I，II不一样，不用dp，用递归。

每个节点都有两个选择，即选当前这个节点或者不选当前这个节点。如果选当前节点则不能选左右子节点，如果不选当前节点，则可以选左右子节点。所以对于每个节点，先递归求解其左右节点的值，若不选当前节点，则其最大值为max(选左节点，不选左节点)+max(选右节点，不选右节点)；若选当前节点，则其最大值为不选左节点＋不选右节点＋当前节点值。最后再在这两个里面取较大的那个即可。

代码如下：

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    public int houseRobber3(TreeNode root) {
        // write your code here
        int[] ans = dp(root);
        return Math.max(ans[0], ans[1]);
    }

    private int[] dp(TreeNode root){
        if(root == null){
            return new int[]{0, 0};
        }

        int[] left = dp(root.left);
        int[] right = dp(root.right);

        //0表示不选当前节点，1表示选当前节点
        int[] now = new int[2];
        now[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        now[1] = left[0] + right[0] + root.val;
        return now;
    }
}