337. House Robber III

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 1:

Input: [3,2,3,null,3,null,1]

3
    / \
   2   3
    \   \ 
     3   1

Output: 7

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

Example 2:

Input: [3,4,5,1,3,null,1]

3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9

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

难度：medium

题目：

小偷又发现了一个新的地方来实施的偷盗计划。 这个地方只有一个入口叫“根”。除了这个根之外，每个房间有且仅有一个父房间。一番游览过后，聪明的小偷意识到这里所有的房子形成了一棵二叉树。如果在同一晚上有任何两个相邻的房子遭遇偷盗就会触发警报。

在这个晚上小偷如何决策在不触发警报的情况下获取最大的盗资。

思路：

二叉树遍历

Runtime: 733 ms, faster than 27.11% of Java online submissions for House Robber III.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // rob root,     g(root)     = root.val + f(root.left.left) + f(root.left.right) + f(root.right.left) + f(root.right.right)
    // not rob root, g(not_root) = f(root.left) + f(root.right);
    // f(root) = Math.max(g(root), g(not_root))
    
    public int rob(TreeNode root) {
        if (null == root) {
            return 0;
        }

        TreeNode left = root.left;
        int leftSum = (null == left) ? 0 : (rob(left.left) + rob(left.right));
        
        TreeNode right = root.right;
        int rightSum = (null == right) ? 0 : (rob(right.left) + rob(right.right));
        
        return Math.max(root.val + leftSum + rightSum, rob(left) + rob(right));
    }
}