05 August 2008
Given a binary search tree and the lowest and highest boundaries as 1
L
1
R
1
[L, R]
Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
给一个边界返回[L, R]，修剪给定的BST，所有不在范围内的结点都应该被剪掉，但是剩下的应该还是BST，左<=根<=右，如果是先遍历一遍BST，把符合要求的结点放入到一个Array里面，然后再重建一个新的BST，这样的想法可能会改变原来BST的总体结构；
所以用另外一种思路，在遍历的过程就对二叉树进行修剪，在递归的过程中判定根结点是否在范围中，如果根结点的值小于L，就返回根结点的右子结点调用递归的值；如果根结点大于R，就返回根结点的左子结点调用递归函数的值；如果根结点在范围内，就将起左右子结点同时更新为对其左右子结点调用递归函数的值，最后返回root。
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return null;
}
if (root.val < L) {//左边的结点都不用看了
return trimBST(root.right, L, R);
}
if (root.val > R) {//右边的结点都不用看了
return trimBST(root.left, L, R);
}
//root的值在L和R中间的时候
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
同样，也可以用非递归while的办法来代替递归过程
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return null;
}
while (root.val < L || root.val > R) {
root = (root.val < L) ? root.right : root.left;
}
TreeNode current = root;
while (current != null) {
while (current.left != null && current.left.val < L) {
current.left = current.left.right;//太小，移向右边
}
current = current.left;
}
current = root;
while (current != null) {
while (current.right != null && current.right.val > R) {
current.right = current.right.left;//太大，移向左边
}
current = current.right;
}
return root;
}
}