Kth Smallest Element in a BST
这题考察的就是 BST 的性质: in order = sorted.
另一种应对多次查询的好办法是 augmented binary tree; 第一次用 O(n) 的时间统计记录一下每个 node 左子树节点个数，后面的每次查询就可以 O(height) 的时间搜索了。
public class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if(--k == 0) return node.val;
cur = node.right;
}
return root.val;
}
}
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
思路一, 对node计数, 这样找左边第K个或者右边第k-left-1个
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int left = nodeCount(root.left); // this value can be saved in the root node
if(left + 1 == k) {
return root.val;
} else if (left + 1 < k) {
return kthSmallest(root.right, k - left - 1);
} else {
return kthSmallest(root.left, k);
}
}
private int nodeCount(TreeNode root) {
if(root == null) {
return 0;
}
return 1 + nodeCount(root.left) + nodeCount(root.right);
}
}
维护一个大小为 k 的 max heap，一直有 insert 的时候好办；有 delete 而且删掉的 node 又在 heap 里就只好找一下 in order successor 了。
PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
Inorder Successor in BST
递归
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return root;
if(root.val<=p.val){
return inorderSuccessor(root.right, p);
}else{
TreeNode left = inorderSuccessor(root.left, p);
return left!=null? left : root;
}
迭代
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode succ = null;
while(root!=null){
if(root.val>p.val){
succ = root;
root = root.left;
}
else
root = root.right;
}
return succ;
}
对binary tree通用的方式, inorder traversal时引入变量isreachedP, 第一次碰到P node时设为true, isreachedP为true时, 返回下一个node
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
boolean reachedP = false;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if(reachedP) return node;
if(node == p) reachedP = true;
cur = node.right;
}
return null;
}
}
Convert Sorted Array to Binary Search Tree
利用 BST inorder = sorted 的性质，一道很有意思的递归题。
在 BST 里多用区间的思想思考问题。
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int start, int end){
if(start > end) return null;
if(start == end) return new TreeNode(nums[start]);
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, start, mid - 1);
root.right = helper(nums, mid + 1, end);
return root;
}
}
Verify Preorder Sequence in Binary Search Tree
只给定一个 preorder 顺序是无法生成唯一 binary tree 的，也可以生成多个 valid BST.
所以这题的题意需要澄清下，正确意思是，给定一个 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 要考虑。传递参数时, 只需要传递区间start和end就可以了.
- O(nlogn) time and O(1) space
递归
public class Solution {
public boolean verifyPreorder(int[] preorder) {
if(preorder==null || preorder.length==0) return true;
return isValid(preorder, 0, preorder.length-1);
}
public boolean isValid(int[] preorder, int start, int end){
if(end-start<=1) return true;
int breakpoint=start+1;
int root = preorder[start];
while(breakpoint<=end&&preorder[breakpoint]<root) breakpoint++;
for(int i=breakpoint;i<=end;i++){
if(preorder[i]<root) return false;
}
return isValid(preorder, start+1, breakpoint-1) && isValid(preorder, breakpoint, end);
}
}
迭代 (Stack)
用stack来维护一个单调的递减的序列, low维护下限, 如preorder序列是[10,5,4,3, 7, 11, 16, 14, 17], 当单调递减的[10,5,4,3]压入队列, low=minvalue; 当遇到7时, 弹出[5,4,3], 栈变为[10,7], low=7, 此时后面的元素必须大于low.
时间复杂度O(n), 空间复杂度O(n)
public boolean verifyPreorder(int[] preorder) {
Stack<Integer> stack = new Stack<Integer>();
int low = Integer.MIN_VALUE;
for(int i=0;i<preorder.length;i++){
if(preorder[i]<low) return false;
//if(!stack.isEmpty()) System.out.println(preorder[i] + " " + stack.peek());
while(!stack.isEmpty() && preorder[i]>stack.peek())
low = stack.pop();//用low来存上一次popout遍历的value，后面的数字不能小于它
stack.push(preorder[i]);
}
return true;
}
Recover Binary Search Tree
Java 里一切都是 pass by value，当传入的是 object reference 的时候，实际传入的就是 object 的内存地址。
因此，带泛型的各种数据结构，Stack, List 等，即使里面放的都是 TreeNode 并且进行了各种 add/remove/pop 操作，对这些 object 的修改也会反映到原来的 Tree 上。
Hard 题，因为得 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.
两种case: 1. 交换两个相邻的元素 2. 两个元素不相邻 本质就是一个inorder traversal
public void recoverTree(TreeNode root) {
Stack<TreeNode> stack= new Stack<TreeNode>();TreeNode cur =root; TreeNode pre =null;TreeNode first =null; TreeNode mid = null; TreeNode last = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
cur = stack.pop();
if(pre!=null && cur.val<pre.val){
if(first==null){
first = pre;
mid = cur;
}
else
last = cur;
}
pre = cur;
cur = cur.right;
}
//case1: The swapped nodes are not adjacent in the inorder traversal of the BST.
//For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
//The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
if(first!=null && last==null) swapval(first, mid);
//The swapped nodes are adjacent in the inorder traversal of BST.
//For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
//The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
else if(first!=null && last!=null) swapval(first, last);
}
public void swapval(TreeNode mid, TreeNode last) {
// TODO Auto-generated method stub
int tmp = mid.val;
mid.val=last.val;
last.val=tmp;
}
遍历和迭代更简洁的写法在论坛这个帖子里写的非常好。
找错误元素可以简化成一次遍历，第一次找到违章元素，prev 是 swapped; 然后继续扫，第二次看到违章元素，cur 是 swapped.
递归版：
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);
}
迭代版：
public class Solution {
public void recoverTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
TreeNode prev = null;
TreeNode p = null;
TreeNode q = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if(prev != null && node.val <= prev.val){
if(p == null) p = prev;
q = node;
}
/* 上面这里如果写成这样，会在 [0,1] 的 case 上挂掉
原因是只有两个 node 的情况下 q 还没来得及被赋值
就结束了，于是 q == null 会导致无法 swap.
拿掉那个 else 可以保证不管怎样 q 指向 cur node.
if(p == null){
p = prev;
} else {
q = node;
}
*/
prev = node;
cur = node.right;
}
swap(p, q);
}
private void swap(TreeNode p, TreeNode q){
if(p == null || q == null) return;
int temp = p.val;
p.val = q.val;
q.val = temp;
}
}
Find Mode in Binary Search Tree
BST inorder traversal, 注意while loop出来后还要再判断末尾元素, 代码有点丑, 打完泰拳累晕累晕的
然而这道题要求是O(1) space的,这种情况首先想到moris traversal. 同时不能存储所有碰到的元素, 否则是O(N) space的. 所以in order遍历的时候就要handle元素.
public class Solution {
int max = 0;
int curval;
int count = 0;
ArrayList<Integer> ans = new ArrayList<Integer>();
public int[] findMode(TreeNode root) {
dfs(root);
int[] modes = new int[ans.size()];
for(int i=0;i<modes.length;i++) modes[i] = ans.get(i);
return modes;
}
public void handle(int val){
if(val!=curval){
curval = val;
count =0;
}
count++;
if(count==max) ans.add(val);
else if(count>max){
max = count;
ans.clear();ans.add(val);
}
}
public void dfs(TreeNode root){
if(root==null)
return;
dfs(root.left);
handle(root.val);
dfs(root.right);
}
}
Moris Traversal
Count of Smaller Numbers After Self
非常好的一道题，用BST直接构造。每个node count存duplicate，leftCount存遇到过的数字。[3, 2, 2, 6, 1],
1(0, 1)
\
6(3, 1)
/
2(0, 2)
\
3(0, 1)
class TreeNode{
int val;
int count = 0;
int leftCount = 0;
int rightCount = 0;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
count=1;
}
}
public class Solution {
public int insertNode(TreeNode root, int val){
int rtn = 0;
while(root!=null){
if(root.val>val){
root.leftCount++;
if(root.left==null){
TreeNode node = new TreeNode(val);
root.left = node;
return rtn;
}
root = root.left;
}
else if (root.val==val){
root.count++;
rtn += root.leftCount;
return rtn;
}
else{
rtn += root.count + root.leftCount;
if(root.right==null){
TreeNode node = new TreeNode(val);
root.right = node;
return rtn;
}
root = root.right;
}
}
return rtn;
}
public List<Integer> countSmaller(int[] nums) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(nums.length<1) return result;
TreeNode root = new TreeNode(nums[nums.length-1]);
result.add(0);
for(int i=nums.length-2;i>=0;i--){
int rtn = insertNode(root, nums[i]);
result.add(0, rtn);
}
return result;
}
}
Count of Range Sum
这道题， 看似简单，O（n＊n）的方法很好想到，然而O（nlogn）并不好想到。
这道题试图用segment tree写，写到最后search的时候发现不对劲，传统search会遗漏掉一些空间。本质因为传统search传入的是lowidx和highidx，所以query的时候可以有效剪枝。而这里是用lower bound和higher bound进行的剪枝。没法有效进行。
参考了论坛的segment tree解法，非常的不直观，需要对sum数组建立segment tree，再查询。查询的方式也很奇怪，花了时间研究后放弃这个仅有17票的解法。
merge sort的思路是这样的
首先建立sum［n＋1］数组。如［1，2，3］，sum数组为［0，1，3，6］，sum［j］－sum［i］可求出range sum。
递归调用merge（start，mid）和merge（mid，end），此时（start，mid）是“单调有序”的sum数组，（mid，end）是“单调有序”的sum数组，并且（mid，end）的sum index 一定比（start，mid）的sum index大。最重要的性质。
求解用当前左半部分（start，mid）和右半部分（mid，end）构造 range sum， 有多少合法的解决。 这里又利用到了two pointers的思路。 对左半部分每个i小于mid进行枚举，在右半部分找到对应的j和k，满足sum[j]-sum[i]<=upper, lower<=sum[k]-sum[i], 因为右半部分单调，j>=k.
最后记得将左右半部分merge sort，供下次使用。
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] sums = new long[nums.length+1];
for(int i=0;i<nums.length;i++){
sums[i+1]=sums[i]+nums[i];
}
int count = mergeCount(sums, 0, nums.length+1, lower, upper);
return count;
}
public int mergeCount(long[] sums, int start, int end, int lower, int upper){
if(end-start<=1) return 0;
int mid = start+(end-start)/2;
int count = mergeCount(sums, start, mid, lower, upper)+mergeCount(sums, mid, end, lower, upper);
long[] cache = new long[end-start]; int c = 0;
int j = mid; int k=mid; int i = start; int l = mid;
while(i<mid){
while(k<end&&sums[k]-sums[i]<lower) k++;
while(j<end&&sums[j]-sums[i]<=upper) j++;
while(l<end&&sums[l]<=sums[i]) cache[c++]=sums[l++];
count+=j-k;
cache[c] = sums[i];
i++;c++;
}
System.arraycopy(cache, 0, sums, start, l - start);
return count;
}
}
这道题我最喜欢的最简单最直接的方式是利用和 count of smaller numbers after itself的思路，对sum数组建立BST，然后对于每一个sum［j］，查询有多少sum［i］在［sum［j］－upper，sum［j］－lower］的range里。 注意查询的时候先查询再插入。
public class Solution {
class TreeNode{
int count;
int leftCount;
long val;
TreeNode left;
TreeNode right;
public TreeNode(long val){
this.val = val;
count = 1;
leftCount = 0;
}
}
public void insert(TreeNode node, long val){
while(node!=null){
if(node.val==val){
node.count++;
return;
}
else if(node.val<val){
if(node.right!=null) node = node.right;
else {node.right = new TreeNode(val); return;}
}
else if(node.val>val){
node.leftCount++;
if(node.left!=null) node = node.left;
else {node.left = new TreeNode(val);return;}
}
}
}
public int getBound(TreeNode node, long val, boolean include){
int count = 0;
while(node!=null){
if(node.val==val){
count+=node.leftCount;
count+=include?node.count:0;
return count;
}
else if(val>node.val){
count+=node.count+node.leftCount;
node = node.right;
}
else{
node = node.left;
}
}
return count;
}
public int countRangeSum(int[] nums, int lower, int upper) {
TreeNode root = new TreeNode(0); long sum = 0; int count=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
count += getBound(root,sum-lower, true)-getBound(root, sum-upper, false);
// System.out.println("i" + i + "count: "+ count);
insert(root, sum);
//System.out.println("root");
}
return count;
}
}
Reverse Pairs
一个套路的，一样照葫芦画瓢撸了一个BST，注意2*nums［i］再转long会溢出，过了37/130test cases后TLE。复杂度是O（nlogn）没毛病。可以看出以上三个问题的抽象表述，如果要找一个数组之间的pair，count关系，利用BST可以有效进行搜索。
BST solution is no longer acceptable, because it's performance can be very bad, O(n^2) actually, for extreme cases like [1,2,3,4......49999], due to the its unbalance, but I am still providing it below just FYI.
注意worst case可以变成o(n^2).
public class Solution {
class TreeNode{
long val;
int count;
int rightCount;
TreeNode left;
TreeNode right;
public TreeNode(long val){
this.val = val;
this.count = 1;
this.rightCount = 0;
}
}
public void insert(TreeNode node, long val){
while(node!=null){
if(node.val==val){
node.count++;
return;
}
else if(node.val>val){
if(node.left!=null) {node = node.left;}
else{
node.left = new TreeNode(val);return;
}
}
else{
node.rightCount++;
if(node.right!=null) {node = node.right;}
else{
node.right = new TreeNode(val);return;
}
}
}
}
public int search(TreeNode node, long val){
int count =0; val*=2;
while(node!=null){
if(node.val==val){
return count+node.rightCount;
}
else if(node.val>val){
count+=node.count+node.rightCount;
node = node.left;
}
else{
node = node.right;
}
}
return count;
}
public int reversePairs(int[] nums) {
TreeNode root = new TreeNode(0); root.count = 0;
int count = 0;
for(int i=0;i<nums.length;i++){
count +=search(root, nums[i]);
insert(root, nums[i]);
}
return count;
}
}
再撸了一个mergesort＋twopointer版本，注意mid细节的处理，左半部分是（start，mid）右半部分是（mid＋1，end）为了省事，mergesort那部分用arraysort了。
public class Solution {
public int reversePairs(int[] nums) {
int count = mergeCount(nums, 0, nums.length-1);
return count;
}
public int mergeCount(int[] nums, int start, int end){
if(start>=end) return 0;
int mid = start + (end-start)/2;
int count = 0;
count = mergeCount(nums, start, mid)+mergeCount(nums, mid+1, end);
int j = mid+1;
for(int i=start;i<=mid;i++){
while(j<=end&&nums[i]/2.0>nums[j]) j++;
count+=j-(mid+1);
}
Arrays.sort(nums, start, end+1);
return count;
}
}
K Inverse Pairs Array
这道Inverse Pairs 换了一种描述方式后，就成了一道dp的题。dp[n,k]代表n个数字里可以形成k个pairs，那么我们可以得到一种递推关系，dp[n,k] = dp[n-1, k] + dp[n-1, k-1] +....+ dp[n-1, max(0, k-(n-1))]. 举个例子，dp[3,2] 可以由
dp [2,2] = 0
dp[2][2]=1 [2,1]==>[2,1,3]
dp[2,0] = 1 [1,2] ==>[3,1,2].
dp[n,k]总可以让最后加入的字符n插入到之前的某一位置，这样会在之前的基础上增加x个reverse pairs，x最多为n－1个pair。所以我们最多可以递归到dp[n-1, k-(n-1)]这个位置。当k很小时，k-(n-1)<0, 所以取max(0, k-(n-1)). 这题注意要取mod。long保存dp[][]数组。
public class Solution {
public int kInversePairs(int n, int k) {
int mod = 1000000007;
long [][] dp =new long[n+1][k+1];
for(int i=1;i<=n;i++){
dp[i][0] = 1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++){
int t = j; int lower = Math.max(0, j-(i-1));
while(t>=lower){
dp[i][j] += dp[i-1][t];
t--;
}
dp[i][j] = (dp[i][j]+mod) % mod;
}
// for(int i=0;i<=n;i++)
// System.out.println(Arrays.toString(dp[i]));
return (int)dp[n][k];
}
}
dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]
从上两行可推出 dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]
dp[n][k] = dp[n][k-1]+dp[n-1][k] - dp[n-1][k-n]
优化time complexity
Minimum Absolute Difference in BST
撸了最简单迭代in order traversal。太久没看有点忘，还好底子好，捡起来很快。
public class Solution {
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
int prev = -1; int diff = Integer.MAX_VALUE;
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(prev!=-1)
diff = Math.min(diff, cur.val-prev);
prev = cur.val;
cur=cur.right;
}
return diff;
}
}
递归版本，O(1) space complexity.
public class Solution {
int min = Integer.MAX_VALUE;
Integer prev = null;
public int getMinimumDifference(TreeNode root) {
if (root == null) return min;
getMinimumDifference(root.left);
if (prev != null) {
min = Math.min(min, root.val - prev);
}
prev = root.val;
getMinimumDifference(root.right);
return min;
}
}
follow up: 如果树不是BST呢？这个时候我们可以利用一个TreeSet来maintain order。
public class Solution {
TreeSet<Integer> set = new TreeSet<>();
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root == null) return min;
if (!set.isEmpty()) {
if (set.floor(root.val) != null) {
min = Math.min(min, root.val - set.floor(root.val));
}
if (set.ceiling(root.val) != null) {
min = Math.min(min, set.ceiling(root.val) - root.val);
}
}
set.add(root.val);
getMinimumDifference(root.left);
getMinimumDifference(root.right);
return min;
}
}