Binary Search Tree in Interview

Binary Search Tree (简称BST) 是最简单的搜索树,很多高级树用法都是以它为基础。因为设计它的算法很多都很巧妙,记得在面试的时候突然遇到一道BST的题卡住了。由于BST的结构特殊,所以有关它的题目都很灵活,想借此机会总结一下。

递归与递推

众所周知,BST是天生具有递归特性的,因为的BST的任一子树都是BST。所以很多题目都是利用这一性质。比如将BST有序打印出来就可以使用inorder遍历:

1
2
3
4
5
6
7
8
public void recursive(TreeNode root) {
if (root == null) return;
recursive(root.left);
/*
Do something...
*/
recursive(root.right);
}

当然也可以通过栈来改写为递推,这里是将未处理的结点存入栈中。这里需要介绍一种pushAll操作。就是将该结点的所有左结点全部压入栈。然后每次取出结点后对右结点进行pushAll操作。Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.add(cur.val);
cur = cur.right;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
}
return ans;
}

了解到这个特性后,我们就可以将BST改写成Iterator - next()取出下一个最小值,hasNext()是否存在结点。Binary Search Tree Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class BSTIterator {
private Deque<TreeNode> stack;

public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
pushAll(root);
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}

/** @return the next smallest number */
public int next() {
TreeNode cur = stack.pop();
pushAll(cur.right);
return cur.val;
}

private void pushAll(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
}

在Java的Iterator是也可以支持remove()操作 - 删除上一个访问的结点。BST删除结点的操作也可以用递归算法来解决(当然也可用平衡二叉树删除结点进行分类的解法,但是递归的解法更加巧妙)。首先我们找到被删除的结点,然后把它替换成其右子树的最小值m(目的是为了保证删除后的右子树满足比当前结点大)。然后我们再递归删除右子树的m结点。Delete Node in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode min = findMin(root.right);
// copy
root.val = min.val;
root.right = deleteNode(root.right, min.val);
}
}
return root;
}

private TreeNode findMin(TreeNode root) {
TreeNode cur = root;
while (cur.left != null) {
cur = cur.left;
}
return cur;
}

查找

上文中我们知道BST是可以有序输出的,所以很多针对有序数据的算法都可以套在BST上。比如,二分查找,第k大问题,等等。

如果查找的结点存在于BST上,我们很容易可以将它找出。但是如果需要查找的结点不存在与树上,我们希望返回最接近的结点,这种问题该如何解决呢?首先我们要想一个问题,对于一个在BST上的结点,比它大的值可能存在于哪里?应该是存在于这个结点的右子树或父结点(如果存在)的右子树。但是这么思考的问题是我们需要跟踪父结点的情况,这个如果不借助其他数据结构存储很难实现。我们不如换一种思路:当访问到结点时,如果值大于target就找保存左子树的最接近target的值,然后取这两个值最接近target的一个;反之就从右子树来找。同样借助递归的特性我们可以解决这个问题。Closest Binary Search Tree Value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int closestValue(TreeNode root, double target) {
if (root == null) {
return -1;
}
if (Math.abs((double)root.val - target) < 1e-6) {
return root.val;
}
if ((double)root.val < target && root.right != null) {
int r = closestValue(root.right, target);
if (Math.abs(target - (double)r) < Math.abs(target - (double)root.val)) {
return r;
}
return root.val;
} else if ((double)root.val > target && root.left != null) {
int r = closestValue(root.left, target);
if (Math.abs(target - (double)r) < Math.abs(target - (double)root.val)) {
return r;
}
return root.val;
}
return root.val;
}

借用这种想法,我们还可以解决类似的问题。比如将BST分成两个BST,一个所有的值小于等于target,另一个大于target。对于当前结点如果小于等于target,其左边子树都是小于等于target,所以将右子树分成的结果的第一部分连接到当前结点的右边;如果大于target,说明右子树都是大于target,需要将左子树的结果的第二部分连入左边。Split BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode[] splitBST(TreeNode root, int V) {
if (root == null) {
return new TreeNode[]{null, null};
}
TreeNode[] res;
if (root.val <= V) {
res = splitBST(root.right, V);
root.right = res[0];
res[0] = root;
} else {
res = splitBST(root.left, V);
root.left = res[1];
res[1] = root;
}
return res;
}

对于第k大的问题,可以通过inorder遍历来解决。Kth Smallest Element in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int count = 0;
public int kthSmallest(TreeNode root, int k) {
return solve(root, k);
}

private int solve(TreeNode root, int k) {
if (root == null) {
return -1;
}
int r = solve(root.left, k);
if (r != -1) return r;
count++;
if (count == k) {
return root.val;
}
r = solve(root.right, k);
return r;
}

另一种变形是,在BST找到接近target的k个数。这个可以通过inorder来找到,但是这里介绍一种高效的方法借助额外的数据结构来解决。通过栈来存储比target小的结点,另一个栈存储大于等于target的结点。然后用类似two pointer的方法找到接近target的k个数。Closest Binary Search Tree Value II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Deque<TreeNode> greater = new ArrayDeque<>(), less = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null) {
if (cur.val < target) {
less.push(cur);
cur = cur.right;
} else {
greater.push(cur);
cur = cur.left;
}
}
List<Integer> list = new ArrayList<>();
while (k > 0) {
if (greater.isEmpty() && less.isEmpty()) {
break;
} else if (greater.isEmpty()) {
list.add(lessNext(less));
} else if (less.isEmpty()) {
list.add(greaterNext(greater));
} else if (Math.abs(less.peek().val - target) < Math.abs(greater.peek().val - target)) {
list.add(lessNext(less));
} else {
list.add(greaterNext(greater));
}
k--;
}
return list;
}

private int lessNext(Deque<TreeNode> stack) {
TreeNode top = stack.pop();
int r = top.val;
top = top.left;
while (top != null) {
stack.push(top);
top = top.right;
}
return r;
}

private int greaterNext(Deque<TreeNode> stack) {
TreeNode top = stack.pop();
int r = top.val;
top = top.right;
while (top != null) {
stack.push(top);
top = top.left;
}
return r;
}