leetcode450. Delete Node in a BST

yzd 发布于2019-08-16 17:33 / 1570人阅读

摘要：题目要求假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。思路和代码二叉搜索树的特点是，对于树中的任何一个节点，一定满足大于其所有左子节点值，小于所有其右子节点值。

题目要求

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

Example:

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

    5
   / 
  3   6
 /    
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / 
  4   6
 /     
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / 
  2   6
      
    4   7

假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。

思路和代码

二叉搜索树的特点是，对于树中的任何一个节点，一定满足大于其所有左子节点值，小于所有其右子节点值。当删除二叉搜索树中的一个节点时，一共有三种场景：

该该节点为叶节点，此时无需进行任何操作，直接删除该节点即可

该节点只有一个子树，则将唯一的直接子节点替换掉当前的节点即可

该节点既有做左子节点又有右子节点。这时候有两种选择，要么选择左子树的最大值，要么选择右子树的最小值填充至当前的节点，再递归的在子树中删除对应的最大值或是最小值。

对每种情况的图例如下：

1. 叶节点
    5
   / 
  2   6
      
    4   7 （删除4）
结果为：
    5
   / 
  2   6
       
        7
        
2. 只有左子树或是只有右子树
    5
   / 
  3   6
 /    
2   4   7（删除6）
结果为
    5
   / 
  3   6
 /    
2   4   

3. 既有左子树又有右子树
    6
   / 
  3   7
 /    
2   5   8 （删除6）
   /
  4
首先找到6的左子树中的最大值为5，将5填充到6的位置
    5
   / 
  3   7
 /    
2   5   8 （删除5）
   /
  4
接着递归的在左子树中删除5，此时5满足只有一个子树的场景，因此直接用子树替换即可
    5
   / 
  3   7
 /    
2   4   8 （删除5）

代码如下：

    public TreeNode deleteNode(TreeNode cur, int key) {
        if(cur == null) return null;
        else if(cur.val == key) {
            if(cur.left != null && cur.right != null) {
                TreeNode left = cur.left;
                while(left.right != null) {
                    left = left.right;
                }
                cur.val = left.val;
                cur.left = deleteNode(cur.left, left.val);
            }else if(cur.left != null) {
                return cur.left;
            }else if(cur.right != null){
                return cur.right;
            }else {
                return null;
            }
        }else if(cur.val > key) {
            cur.left = deleteNode(cur.left, key);
        }else {
            cur.right = deleteNode(cur.right, key);
        }
        return cur;
    }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74579.html

[LeetCode] 450. Delete Node in a BST

Problem Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divi...

spacewander 2019-08-16 13:36 评论0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 评论0 收藏0
[Leetcode-Tree]Delete Node in a BST

摘要：解题思路我们可以用递归来查找，在找到需要删除的节点后，我们需要分情况讨论节点是叶子节点，直接返回节点有一个孩子，直接返回孩子节点有两个孩子，我们要将右子树中最小的节点值赋值给根节点，并在右子树中删除掉那个最小的节点。 Delete Node in a BSTGiven a root node reference of a BST and a key, delete the node w...

wangjuntytl 2019-08-16 10:26 评论0 收藏0
[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解题思路本题需要找的是第小的节点值，而二叉搜索树的中序遍历正好是数值从小到大排序的，那么这题就和中序遍历一个情况。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 评论0 收藏0
[Leetcode] Kth Smallest Element in a BST 二叉搜索树第k小节

摘要：中序遍历复杂度时间空间思路因为左节点小于根节点小于右节点，二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式，我们就可以在找到第小节点时马上退出。这样我们就可以用二叉树搜索的方法来解决这个问题了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

Dean 2019-08-14 12:26 评论0 收藏0