总结了一下删除二叉搜索树节点的迭代和递归方法。

1、二叉搜索树

二叉搜索树的重要性质：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉搜索树；

2、删除二叉搜索树的节点

删除二叉搜索树的节点有三种情况。
（1）删除节点没有子节点；
（2）删除节点只有一个子节点；
（3）删除节点有两个子节点。
如下是一棵二叉搜索树：

第一种情况，比如删除节点4，只要把当前节点4直接删除即可。
第二种情况，比如删除节点5，只要把节点5的左子树挂到节点5的父节点上。
第三种情况，比如删除节点3，我们要在节点3的右子树中找到大于3的最小节点，在这儿是节点4。然后用找到的最小节点4赋值给节点3，最后再删掉节点4即可。
下面使用迭代和递归两种方法来解决问题。

2.1、迭代

deleteNode函数主要找到删除节点的位置。其中node是要删除的节点，pre是删除节点的父节点。
del函数是删除节点函数。分为三种情况：
（1）要删除的节点没有子节点时，就返回null；
（2）要删除的该节点只有左子树或只有右子树时，就返回要删除节点的左子树或右子树；
（3）要删除节点有两个子节点时，就要将删除节点右子树中的最小值赋值给要删除节点，然后删去最小节点。这里还有两种情况要讨论，这部分代码如下：

1
2
3
4
5
6
7
8
9
let pre = node;
let cur = node.right;
while(cur.left){
    pre = cur;
    cur = cur.left;
}
node.val = cur.val;
console.log(pre.left);
pre === node ? pre.right = cur.right : pre.left = cur.right;

这段代码中cur是找到的最小节点，node是要删除节点，pre是最小节点的父节点。因为最后要删去cur所以，还是需要记录它的父节点pre。
如果是删除下图中的根节点6，此时pre===node。

1
2
3
if(pre===node){
    pre.right=cur.right;
}

如果是删除下图中的节点3，那么pre是节点5。

1
2
3
if(pre !== node){
    pre.left = cur.right;
}

完整代码和注释如下：

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
52
var deleteNode = function(root, key) {
    let node=root;
    let pre=null;
    //找到要删除节点node
    while(node!==null){
        if(node.val===key){
            break;
        }
        pre=node;
        if(node.val>key){
            node=node.left;
        }else{
            node=node.right;
        }
    }
    //没有找到删除节点的情况
    if(node===null){
        return root;
    }
    //pre是当前节点的父节点，这个是删除头结点的情况
    if(pre===null){
        return del(node);
    }
    //删除pre的左节点或者右节点
    if(pre.left&&pre.left.val===key){
        pre.left=del(node);
    }else if (pre.right&&pre.right.val===key){
        pre.right=del(node);
    }
    return root;
};
function del(node){
    //当要删除的该节点没有左右子树
    if(node.left===null&&node.right===null){
        return null;
    }
    //当要删除的该节点只有左子树或只有右子树
    if (!node.left || !node.right) {
        return (node.left) ? node.left : node.right;
    }
    //左右子树都有
    let pre=node;
    let cur=node.right;
    while(cur.left){
        pre=cur;
        cur=cur.left;
    }
    node.val=cur.val;
    console.log(pre.left);
    pre===node?pre.right=cur.right:pre.left=cur.right;
    return node;
}

2.2、递归

先判断根节点是否为空；
然后开始寻找二叉搜索树中key的位置，如果当前节点的值比key大则去找当前节点的左子树，小则找右子树，直到找到与key值相同的节点；
接着判断节点子树的个数，分为节点至多只有一个子树，和有两个子树这两种情况；
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var deleteNode = function(root, key) {
    if(root===null){
        return null;
    }
    if(root.val>key){
        root.left=deleteNode(root.left,key);
    } else if(root.val<key){
        root.right = deleteNode(root.right,key);
    } else{
        //找到key的位置root，当root至多只有一个子树
        if(!root.left||!root.right){
            root=root.left?root.left:root.right;
        }else{
            let cur=root.right;
            while(cur.left){
                cur=cur.left;
            }
            root.val=cur.val;
            root.right=deleteNode(root.right,cur.val);
        }
    }
    return root;
};