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

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

三月 14, 2020

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

 5
/ \
3   6
/ \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
   4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

5
  / \
2   6
 \   \
 4   7

我的思路

二叉搜索树特性:每个节点的左子树比当前节点小,右子树比当前的大.中序遍历是一个递增的序列.
找出要删除的节点和他的父节点,然后再执行删除操作.
删除操作的过程 : 把删除节点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
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null)return null;
        if(root.val==key){//删除根节点特殊判断
            TreeNode newRoot=root.right;
            TreeNode tmp=newRoot;
            if(tmp==null){//没有右子树直接把左子树接过来,下面也一样
                newRoot=root.left;
            }else{
                while(tmp.left!=null){
                    tmp=tmp.left;
                }
                tmp.left=root.left;
            }
            
            return newRoot;
        }

        find(root,key);
        if(keyNodeP==null)return root;//树里面并没有key
        if(keyNodeP.left==keyNode){
            //节点在左子树
            keyNodeP.left=keyNode.right;
            TreeNode tmp=keyNode.right;
            if(tmp==null){//同上
                keyNodeP.left=keyNode.left;
            }else{
                while(tmp.left!=null){
                    tmp=tmp.left;
                }
                tmp.left=keyNode.left;
            }
            
        }else{
        //节点在右子树
            keyNodeP.right=keyNode.right;
            TreeNode tmp=keyNode.right;
            if(tmp==null){
                keyNodeP.right=keyNode.left;
            }else{
                while(tmp.left!=null){
                    tmp=tmp.left;
                }
                tmp.left=keyNode.left;
            }
            
        }
        return root;
    }
    public TreeNode keyNodeP=null;
    public TreeNode keyNode=null;
    public void find(TreeNode root,int key){
        if(keyNodeP!=null)return;
        if(root==null)return;
        if((root.left!=null&&root.left.val==key)){
            keyNodeP=root;
            keyNode=root.left;
            return;
        }else if(root.right!=null&&root.right.val==key){
            keyNodeP=root;
            keyNode=root.right;
            return;
        }else if(key<root.val){
            find(root.left,key);
        }else if(key>root.val){
            find(root.right,key);
        }
    }
    

}

题解区的算法

递归删除二叉搜索树中的节点
这是我看到的代码比较简洁的了

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
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        //如果右子树为null，则返回左子树
        if (root.right == null) {
            return root.left;
        } else {
            //如果右子树不为null，则返回右子树的最小节点
            //node为最小节点，parent为父节点
            TreeNode node = root.right;
            TreeNode parent = root;
            while (node != null && node.left != null) {
                parent = node;
                node = node.left;
            }
            //在右子树上删除node节点
            if (parent.left == node) parent.left = node.right;
            if (parent.right == node) parent.right = node.right;
            //将node节点放在key节点位置上
            node.left = root.left;
            node.right = root.right;
            return node;
        }
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    } else {
        root.left = deleteNode(root.left, key);
    }
    return root;
}

个人感觉这种递归还是不好想,虽然他已经够简单了.
leetcode 50/100