337. House Robber III

  • basic: for each node, you can choose rob or not, based on the parent’s status. return max amount of each choice.
  • dp: keep previous rob information.
class Solution {
// O(n^2) O(n)
public int rob(TreeNode root) {
return dfs(root, false);
}
public int dfs(TreeNode node, Boolean robbed) {
if ( node == null ) return 0;
int rob_node = 0, not_rob_node = 0;
if (robbed) {
not_rob_node = dfs(node.left, false) + dfs(node.right, false);
} else {
rob_node = dfs(node.left, true) + dfs(node.right, true) + node.val;
not_rob_node = dfs(node.left, false) + dfs(node.right, false);
}
return Math.max(rob_node, not_rob_node);
}
}
class Solution2 {
// O(n) O(n)
private Map<TreeNode, Integer> map = new HashMap<>();
public int rob(TreeNode root) {
return dfs(root);
}
public int dfs(TreeNode node) {
if ( node == null ) return 0;
if ( map.containsKey(node) ) return map.get(node);
int val = 0;
if (node.left != null) {
val += dfs(node.left.left) + dfs(node.left.right);
}
if (node.right != null) {
val += dfs(node.right.left) + dfs(node.right.right);
}
val = Math.max(val + node.val, dfs(node.left) + dfs(node.right));
map.put(node, val);
return val;
}
}
class Solution3 {
// O(n) O(1)
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
public int[] dfs(TreeNode node) {
if ( node == null ) return new int[] {0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int[] res = new int[2];
// not rob node
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// rob node
res[1] = node.val + left[0] + right[0];
return res;
}
}
view raw 337_0823.java hosted with ❤ by GitHub

95. Unique Binary Search Trees II

  • foreach 1 to n, generate left and right subtree and combine with current node.
class Solution {
// O(n^2) O(n^2)
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new ArrayList<TreeNode>();
return genTree(1, n);
}
private List<TreeNode> genTree(int start, int end) {
List<TreeNode> list = new ArrayList<>();
if ( start > end ) {
list.add(null);
return list;
}
// this part can be ignored
if ( start == end ) {
list.add(new TreeNode(start));
return list;
}
List<TreeNode> left, right;
for (int i=start; i<=end; i++) {
left = genTree(start, i-1);
right = genTree(i+1, end);
for (TreeNode lnode : left) {
for (TreeNode rnode : right) {
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
list.add(root);
}
}
}
return list;
}
}
view raw 95_0823.java hosted with ❤ by GitHub

111. Minimum Depth of Binary Tree

  • its root to leaf, not to other node. For example (1, 2), the only path is 1->2.
class Solution {
// O(n) O(n/h)
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left, right) + 1;
}
}
view raw 111_0823.java hosted with ❤ by GitHub