【力扣中等】450 - 删除二叉搜索树中的节点

我不是女神ヾ 2023-01-07 03:48 76阅读 0赞

![20210116225840183.jpg][]

## 一、题目描述： ##

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

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

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

示例:

> root = \[5,3,6,2,4,null,7\]  
> key = 3  
> ![20210115133530614.png][]  
> 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
> 
> 一个正确的答案是 \[5,4,6,2,null,null,7\], 如下图所示。  
> ![20210115133552237.png][]  
> 另一个正确答案是 \[5,2,6,null,4,null,7\]。  
> ![20210115133608480.png][]

## 二、解答 ##

### 分析 ###

解题思路：  
首先，这个题目可以根据删除的节点的左右节点来判断。

而找到该节点是非常简单的，因为这棵树是二叉搜索树，而二叉搜索树的特性，左节点的值一定小于该节点值，右节点的值一定大于该节点的值，所以直接搜索就可以找到该值。

所以重点在于怎么判断该节点的左右节点的情况。

大致可以分为四种：

1.  该节点没有左节点，也没有右节点
2.  该节点没有左节点，但有右节点
3.  该节点有左节点，但没有右节点
4.  该节点有左节点，也有右节点

第一种：对于第一种情况，直接将该节点删除即可。  
第二种：对于第二种情况，直接删除节点，将左节点代替该节点。  
第三种：对于第三种情况：直接删除节点，将右节点代替该节点。  
第四种：对于第四种情况，又可以分为三种情况：

1.  该节点的左节点没有右节点，将左节点代替该节点。
2.  该节点的右节点没有左节点，将右节点代替该节点。
3.  对于都有的情况，为了保证二叉搜索树的结构，我们 ① ：可以用该节点的左节点最右节点的值代替该节点；②：也可以用该节点的右节点的最左节点的值代替该节点。

> 而对于最后的情况，也就是第四种情况的第三种情况，  
> 需要注意  
> ①中，如果最右节点还有左节点，我们可以用最右节点的左节点的值代替最右节点所在的位置；  
> ②中，如果最左节点还有右节点，我们可以用最左节点的右节点的值代替最左节点所在的位置。

**再一次总结归纳：**  
其实，最后第四种情况的第三种就包括了前面所有的方面，

在找到该节点后：

1.  如果该节点的左节点不为空，我们用该节点的左节点最右节点的值代替该节点；
2.  否则，如果该节点的右节点不为空，我们可以用该节点的右节点的最左节点的值代替该节点。
3.  否则，将该节点置空。

找到该节点，非常容易，因为左节点的值一定小于该节点值，右节点的值一定大于该节点的值。

所以，从根节点开始遍历

1.  如果遍历到的节点的值大于该值，该值一定处于该节点的右子树，往右遍历即可。
2.  否则，如果遍历到的节点的值小于该值，该值一定处于该节点的左子树，往左遍历即可。
3.  否则，就是找到了该值，在进行上述操作即可。

> 时间复杂度：O(h)，其中 n 为树的高度。

### 代码 ###

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution { 
        public TreeNode deleteNode(TreeNode root, int key) { 
            if(root!=null){ 
                if(root.val == key){ 
                    if(root.left != null){ 
                        root.val = leftMax(root);
                        root.left = deleteNode(root.left, root.val);
                    } else if(root.right != null){ 
                        root.val = rightMin(root);
                        root.right = deleteNode(root.right, root.val);
                    } else {  
                        root = null;
                    }
                }else if(root.val>key){ 
                    root.left = deleteNode(root.left,key);
                }else{ 
                    root.right = deleteNode(root.right,key);
                }
                return root;
            }
            return null;
        }
    
        public int rightMin(TreeNode root) { 
            root = root.right;
            while (root.left != null) root = root.left;
            return root.val;
        }
    
        public int leftMax(TreeNode root) { 
            root = root.left;
            while (root.right != null) root = root.right;
            return root.val;
        }
    }

> 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户  
> 内存消耗：39.2 MB, 在所有 Java 提交中击败了8.92%的用户

## 三、官方解答 ##

class Solution { 
      /* One step right and then always left */
      public int successor(TreeNode root) { 
        root = root.right;
        while (root.left != null) root = root.left;
        return root.val;
      }
    
      /* One step left and then always right */
      public int predecessor(TreeNode root) { 
        root = root.left;
        while (root.right != null) root = root.right;
        return root.val;
      }
    
      public TreeNode deleteNode(TreeNode root, int key) { 
        if (root == null) return null;
    
        // delete from the right subtree
        if (key > root.val) root.right = deleteNode(root.right, key);
        // delete from the left subtree
        else if (key < root.val) root.left = deleteNode(root.left, key);
        // delete the current node
        else { 
          // the node is a leaf
          if (root.left == null && root.right == null) root = null;
          // the node is not a leaf and has a right child
          else if (root.right != null) { 
            root.val = successor(root);
            root.right = deleteNode(root.right, root.val);
          }
          // the node is not a leaf, has no right child, and has a left child 
          else { 
            root.val = predecessor(root);
            root.left = deleteNode(root.left, root.val);
          }
        }
        return root;
      }
    }

> 参考：  
> 1、[题目][Link 1]  
> 2、[官方解答][Link 2]

> 本文首发于CSDN，作者：lomtom  
> 原文链接：**[https://blog.csdn.net/qq\_41929184/article/details/112662236][https_blog.csdn.net_qq_41929184_article_details_112662236]**  
> 个人网站：**[https://lomtom.top][https_lomtom.top]**，公众号：**博思奥园**，同步更新。
> 
> **你的支持就是我最大的动力。**

![20200405094243147.png][]

[20210116225840183.jpg]: /images/20221119/da74360f5d20424597cfd738b61fb820.png
[20210115133530614.png]: /images/20221119/2bdb769730704301b1fea7df9b8ae536.png
[20210115133552237.png]: /images/20221119/8d4952c3f8b94b539a195614a384c9d4.png
[20210115133608480.png]: /images/20221119/e788aed19d744c209a91113d6557dd8a.png
[Link 1]: https://leetcode-cn.com/problems/delete-node-in-a-bst/
[Link 2]: https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/
[https_blog.csdn.net_qq_41929184_article_details_112662236]: https://blog.csdn.net/qq_41929184/article/details/112662236
[https_lomtom.top]: https://lomtom.top
[20200405094243147.png]: https://img-blog.csdnimg.cn/20200405094243147.png