leetcode HouseRobberIII
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import utils.TreeNode;

public class HouseRobberIII {
  /**
   * 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.
   */
  public int rob(TreeNode root) {
    if (root == null) return 0;
    TreeNode left = root.left;
    TreeNode right = root.right;
    if (left == null && right == null) return root.val;
    if (left == null)
      return Math.max(rob(left)+rob(right), root.val + rob(right.left) + rob(left.left));
    if (right == null)
      return Math.max(rob(left)+rob(right), root.val + rob(left.left) + rob(left.right));
    return Math.max(rob(left)+rob(right), root.val + rob(left.left) + rob(left.right) + rob(right.left) + rob(left.left));

  }
}