用时 ：20min

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

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

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

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