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
};