96. Unique Binary Search Trees
给定 n 个 node 之后，直接看 inorder 数组【1, 2, 3, 4 .. n-1, n】
那么选任意位置的元素为 root，都可以建出来一个 valid BST，左子树为 index 左边的 subarray，右子树为 index 右边的 subarray.
于是这就变成了一个利用递归结构的“组合”问题了，解的数量左右相乘。inorder 是 BST 的灵魂啊。
public class Solution {
public int numTrees(int n) {
int[] count = new int[n + 2];
count[0] = 1;
count[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
count[i] += count[j] * count[i - 1 - j];
}
}
return count[n];
}
}
95. Unique Binary Search Trees II
Java 带泛型的 Collections 确实是可以放 null 的， 比如 Queue, List...
在这题里最两边的情况下，list 里直接加个 null 作为 node 用就可以让代码变得非常简洁。
public class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> result = new ArrayList<>();
if (n == 0) return result;
result = build(1, n);
return result;
}
private List<TreeNode> build(int start, int end) {
List<TreeNode> result = new ArrayList<>();
if (start > end) {
result.add(null);
return result;
}
for (int i = start; i <= end; ++i) {
List<TreeNode> left = build(start, i - 1);
List<TreeNode> right = build(i + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}
270. Closest Binary Search Tree Value
需要考虑的是状态的不连续性，所谓 “最近的点”，可能是 parent ，可能是 child，可能在左边，也可能在右边。
所以一要存好 prev;
二要两边都探，不能沿着一边硬走。
用区间的思想去理解的话，每个 node 都有自己的 valid 区间，区间与区间是重合的。对于给定 target，我们先要找到 target 是什么，然后决定 target 到底靠近重合区间的左边还是右边。
另外Integer类型可以封装int和double。
public class Solution {
public int closestValue(TreeNode root, double target) {
return find(root, target, null);
}
private int find(TreeNode root, double target, Integer prev) {
if (root == null) return -1;
if (prev == null) prev = root.val;
if (Math.abs(prev - target) > Math.abs(root.val - target)) {
prev = root.val;
}
if (root.left != null && target < root.val) return find(root.left, target, prev);
if (root.right != null && target > root.val) return find(root.right, target, prev);
return prev;
}
}
下面是论坛上的写法，思想一致，更取巧了一些。
public int closestValue(TreeNode root, double target) {
TreeNode node = (root.val>target)?root.left:root.right;
if (node == null) {
return root.val;
}
int value = closestValue(node, target);
return Math.abs(root.val-target) > Math.abs(value-target)?value:root.val;
}
272. Closest Binary Search Tree Value II
这道题是在二叉树上做 range query.
二叉树上做 range query 普遍要依靠 getPrev() 和 getNext() 函数，或者利用 Parent 指针做 traversal.
但是 BST 不一样，如上题所说， inorder 是 BST 的灵魂。因此这道题可以分为三部分
- 做出 inorder traversal list
- 找 target 对应的 index
- 从 index 两边扫，寻找 k 个元素
时间复杂度 O(n) + O(log n) + O(k) = O(n)
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> inorder = inorder(root);
int index = binarySearch(inorder, target);
List<Integer> list = new ArrayList<Integer>();
int start = index - 1;
int end = index;
while(start >= 0 && end < inorder.size()){
int num = (Math.abs(inorder.get(start) - target) < Math.abs(inorder.get(end) - target))
? inorder.get(start--)
: inorder.get(end++);
list.add(num);
if(list.size() == k) return list;
}
while(start >= 0){
list.add(inorder.get(start--));
if(list.size() == k) return list;
}
while(end < inorder.size()){
list.add(inorder.get(end++));
if(list.size() == k) return list;
}
return list;
}
private int binarySearch(List<Integer> list, double target){
int start = 0;
int end = list.size() - 1;
while(start + 1 < end){
int mid = start + (end - start) / 2;
if(list.get(mid) == target){
return mid;
} else if(target < list.get(mid)){
end = mid;
} else {
start = mid;
}
}
if(target < list.get(start)) return start;
if(target > list.get(end)) return end;
return (Math.abs(list.get(start) - target) < Math.abs(list.get(end) - target)) ? start: end;
}
private List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
List<Integer> left = inorder(root.left);
List<Integer> right = inorder(root.right);
result.addAll(left);
result.add(root.val);
result.addAll(right);
return result;
}
}
Java 內建的 LinkedList 库是双向链表，implements Deque.
这个解法我很喜欢，类似于 sliding window maximum 一样，维护一个大小为 k 的 sliding window，在树上做 inorder traversal，每当 window size == k 但是新 node 值比 head 的值更接近于 target 的时候，就给替换掉。当后来发现新来的 node 不比 head 更接近于 target 的时候，就可以返回结果了，而且因为 LinkedList 继承了 List，连类型转换都不需要。
时间复杂度 O(n) ，还带 early termination，非常简洁高效的解法，比我写的那个速度快，而且简洁明了。
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new LinkedList<Integer>();
helper(root, target, k, res);
return res;
}
private void helper(TreeNode root, double target, int k, List<Integer> res) {
if (root == null) {
return;
}
helper(root.left,target,k,res);
if (res.size()< k) {
res.add(root.val);
} else {
if (Math.abs(res.get(0)-target) > Math.abs(root.val-target)) {
res.remove(0);
res.add(root.val);
} else {
return;
}
}
helper(root.right,target,k,res);
}
255. Verify Preorder Sequence in Binary Search Tree
相关题：331. Verify Preorder Serialization of a Binary Tree
这题的题意需要澄清下，正确意思是，给定一个 preorder sequence，只要这个 sequence 可以生成一个 valid BST，都返回 true
这样我们的判断条件变成了这样，给定 array 如 5(123)(678)，第一个元素一定为 root，后面的比 root 小的连续序列为左子树，比 root 大的连续序列为右子树。
左右子树可以为空，但是不能违反 BST 子树性质。所以如果 > root 的连续数组后面又出现了 < root 的元素，一定是 false.
这题的写法上有点像 quicksort，要注意 index
为了省心起见，这类 subarray 的 divide & conquer 最好把 length <= 2 的直接返回了，不然会多出许多 corner case 要考虑。length <= 2时，因为只有两个点，既可以当做左子树为空也可以当做右子树为空，只要最后返回出valid BST就行。
O(nlogn) time and O(1) space
public class Solution {
public boolean verifyPreorder(int[] preorder) {
return helper(0, preorder.length - 1, preorder);
}
private boolean helper(int start, int end, int[] preorder) {
if (end - start <= 1) return true;
int rightStart = start + 1;
for (int i = start + 1; i <= end; ++i) {
if (preorder[i] < preorder[start]) {
rightStart++;
} else break;
}
for (int i = rightStart; i <= end; ++i) {
if (preorder[i] < preorder[start]) return false;
}
return helper(start + 1, rightStart - 1, preorder) && helper(rightStart, end, preorder);
}
}
99. Recover Binary Search Tree
这道题我先不说Morris遍历的做法，先分析一下这道题。
Java 里一切都是 pass by value，当传入的是 object reference 的时候，实际传入的就是 object 的内存地址。
因此，带泛型的各种数据结构，Stack, List 等，即使里面放的都是 TreeNode 并且进行了各种 add/remove/pop 操作，对这些 object 的修改也会反映到原来的 Tree 上。
因为 O(1) space. 这意味着做个in order存到array里面再扫的做法行不通，连stack也不能用了。
先假设下我们有 inorder array，如何找那对 swapped pair ?
在中间 1234567 -> 1264537
在两端 1234567 -> 7234561
右端 1234567 -> 1237564
左端 1234567 -> 5234167
从左往右找递增序列里面第一个变小的，prev 为 swapped;
从右往左找递减序列里面第一个变大的，prev 为 swapped.
找错误元素可以简化成一次遍历，第一次找到违章元素，prev 是 swapped; 然后继续扫，第二次看到违章元素，cur 是 swapped.
递归写法
我觉得这种写法其实已经足够简洁了，但如果二叉树深度很深，不断递归会造成栈溢出。还是不如Morris的写法。
public void recoverTree(TreeNode root) {
//use inorder traversal to detect incorrect node
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;
public void inOrder(TreeNode root){
if(root == null) return;
//search left tree
inOrder(root.left);
//in inorder traversal of BST, prev should always have smaller value than current value
if(prev != null && prev.val >= root.val){
//incorrect smaller node is always found as prev node
if(first == null) first = prev;
//incorrect larger node is always found as curr(root) node
second = root;
}
//update prev node
prev = root;
//search right tree
inOrder(root.right);
}