669. 修剪二叉搜索树

用时 :20min

与上一道题类似,多的是分了父节点在区间内和不在区间内的情况

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
var trimBST = function(root, low, high) {
var add = function (root,node) {
if (!node || !root) return null
if (node.val > root.val ) {
if (!root.right) {
root.right = node
} else {
add(root.right,node)
}
}
if (node.val < root.val) {
if (!root.left) {
root.left = node
} else {
add(root.left,node)
}
}
}
var walk = function (root) {
if (!root) return root
if (root.val < low || root.val > high) {
var left = walk(root.left)
var right = walk(root.right)
if (!left && !right) {
root = null
} else if (right && left) {
root = right
add(root,left)
} else if (left) {
root = left
} else {
root = right
}
} else {
root.left= walk(root.left)
root.right = walk(root.right)
}
return root
}
return walk(root)
};

看了解析之后发现可以更简单,思路是如果大于右边界,就直接在左分支找; 如果小于左边界,就直接在右分支找。这样就省去了删除节点的步骤

1
2
3
4
5
6
7
8
var trimBST = function(root, low, high) {
if(root == null) return null
if (root.val > high) return trimBST(root.left,low,high)
if(root.val < low) return trimBST(root.right,low,high)
root.left = trimBST(root.left,low,height)
root.right = trimBST(root.right,low,height)
return root
};