leetcode summary 08/23
Contents
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
95. Unique Binary Search Trees II
- foreach 1 to n, generate left and right subtree and combine with current node.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
111. Minimum Depth of Binary Tree
- its root to leaf, not to other node. For example (1, 2), the only path is 1->2.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Author Chen Tong
LastMod 2017-08-23