450. 删除二叉搜索树中的节点

发表于 | 分类于
抓住二叉搜索树的性质可解

用时:30min

题目分两个部分需要解决，搜索和删除

搜索部分就是找到节点，可以根据二叉搜索树的性质来找到需要的节点

删除分三种情况

  1. 只有左孩子，用左孩子代替
  2. 只有右孩子，用右孩子代替
  3. 都没有，则赋值为null （ 由于前面有递归赋值，所以这边可以成功
  4. 都有，则储存左孩子后，用右孩子代替，然后找到左孩子在右边的位置
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
var deleteNode = function(root, key) {
    function  insert(root,node) {
        if (root.val > node.val) {
            if (!root.left) {
                root.left = node
            } else {
                insert(root.left,node)
            }
        } else {
            if (!root.right) {
                root.right = node
            } else {
                insert(root.right,node)
            }
        }
    }
    function search(root) {
      if (!root) {
        return null 
      }
        if (root.val > key) {
            root.left = search(root.left)
        } else if (root.val < key){
            root.right = search(root.right)
        }  else {
            if (!root.left && !root.right) {
                root = null
            } else if (root.left && root.right) {
                var left = root.left
                root = root.right
                insert(root,left)
            } 
            else if (root.left) {
                root = root.left
            } else if (root.right) {
                root = root.right
            }
        }
        return root
    }
    return search(root)
};

需要注意的点

  1. 考虑节点不存在的情况
  2. 删除一个节点的方法，可以给左（右 节点赋值为递归的返回值