LeetCode[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:
3/ \2 3\ \ 3 1Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3/ \4 5/ \ \ 1 3 1Maximum amount of money the thief can rob = 4 + 5 = 9.
recursion + Memorization
复杂度
O(N), O(lgN)思路
对于每一个位置来说，考虑两种情况, Max(child, subchild + root.val).分别对child和subchild再进行recursion计算。用map对已经计算过的node进行保留，避免重复计算。
代码
public int rob(TreeNode root) { // Base case; if(root == null) return 0; if(root.left == null && root.right == null) return root.val; if(map.containsKey(root)) return map.get(root); int child = 0, subchild = 0; if(root.left != null) { child += rob(root.left); subchild += rob(root.left.left) + rob(root.left.right); } if(root.right != null) { child += rob(root.right); subchild += rob(root.right.left) + rob(root.right.right); } int val = Math.max(child, subchild + root.val); map.put(root, val); return val;}