专栏首页爱写BugLeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

题目:

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

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.

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

说明: 要求算法时间复杂度为 O(h),h 为树的高度。

Note: Time complexity should be O(height of tree).

示例:

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

解题思路:

待删除节点在二叉树中的三种情况有:

  1. 如果目标节点没有子节点,我们可以直接移除该目标节点。
  2. 如果目标节只有一个子节点,我们可以用其子节点作为替换。
  3. 如果目标节点有两个子节点,我们需要用其中序后继节点或者前驱节点来替换,再删除该目标节点。

另外二叉搜索树的中序遍历结果为从小到大顺序排列的; 删除节点如果不是叶子节点时, 则应把该节点的值替换为其右子树中最小的一个节点值 (删除节点的后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点的值替换为其左子树中最大的一个节点值 (删除节点的前驱节点), 并在子树中递归删除刚刚替换的节点

你会发现, 二叉搜索树最小节点为该树的最左叶子; 最大节点为该树的最右叶子, 即:

  • 如果 key > root.val,说明要删除的节点在右子树,root.right = deleteNode(root.right, key)。
  • 如果 key < root.val,说明要删除的节点在左子树,root.left = deleteNode(root.left, key)。
  • 如果 key == root.val,则该节点就是我们要删除的节点,则:
    • 如果该节点是叶子节点,则直接删除它:root = null。
    • 如果该节点不是叶子节点且有右节点,则用它的后继节点的值替代 root.val = successor.val,然后删除后继节点。
    • 如果该节点不是叶子节点且只有左节点,则用它的前驱节点的值替代 root.val = predecessor.val,然后删除前驱节点。

Java:

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        // 找到待删除节点后的三种情况
        if (key == root.val) {
            // 删除节点为叶子节点
            if (root.left == null && root.right == null)
                root = null;
            // 删除节点有右子树
            else if (root.right != null) {
                root.val = postNode(root.right);
                root.right = deleteNode(root.right, root.val);
            } else {// 删除节点无右子树但存在左子树
                root.val = preNode(root.left);
                root.left = deleteNode(root.left, root.val);
            }
        } else if (key > root.val)
            root.right = deleteNode(root.right, key);
        else
            root.left = deleteNode(root.left, key);
        return root;
    }
    // 找左子树的最大节点
    private int preNode(TreeNode root) {
        while (root.right != null)
            root = root.right;
        return root.val;
    }
    // 找右子树的最小节点
    private int postNode(TreeNode root) {
        while (root.left != null)
            root = root.left;
        return root.val;
    }
}

Python:

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        # 找到待删除节点后的三种情况
        if root.val == key:
            # 删除节点为叶子节点
            if not root.left and not root.right:
                root = None
            # 删除节点有右子树
            elif root.right:
                root.val = self.postNode(root.right)
                root.right = self.deleteNode(root.right, root.val)
            # 删除节点无右子树但存在左子树
            else:
                root.val = self.preNode(root.left)
                root.left = self.deleteNode(root.left, root.val)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            root.left = self.deleteNode(root.left, key)
        return root
    # 找左子树的最大节点
    def preNode(self, root: TreeNode) -> int:
        while root.right:
            root = root.right
        return root.val
    # 找右子树的最小节点
    def postNode(self, root: TreeNode) -> int:
        while root.left:
            root = root.left
        return root.val

Golang:

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    // 找到待删除节点后的三种情况
    if root.Val == key {
        // 删除节点为叶子节点
        if root.Left == nil && root.Right == nil {
            root = nil
        } else if root.Right != nil {// 删除节点有右子树
            root.Val = postNode(root.Right)
            root.Right = deleteNode(root.Right, root.Val)
        } else {// 删除节点无右子树但存在左子树
            root.Val = preNode(root.Left)
            root.Left = deleteNode(root.Left, root.Val)
        }
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        root.Left = deleteNode(root.Left, key)
    }
    return root
}
// 找左子树的最大节点
func preNode(root *TreeNode) int {
    for root.Right != nil {
        root = root.Right
    }
    return root.Val
}
// 找右子树的最小节点
func postNode(root *TreeNode) int {
    for root.Left != nil {
        root = root.Left
    }
    return root.Val
}

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in...

    爱写bug
  • LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

    给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

    爱写bug
  • LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

    给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

    爱写bug
  • 程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

    Michael阿明
  • Centos7下部署两套python版本并存环境的操作记录

    需求说明: centos7.2系统的开发机器上已经自带了python2.7版本,但是开发的项目中用的是python3.5版本,为了保证Centos系统的正常运行...

    洗尽了浮华
  • Linux工作目录切换命令

    心跳包
  • 【趣学程序】Linux流的重定向

    趣学程序-shaofeer
  • LeetCode 146 LRU Cache

    实现一个缓存机制。很多人的写法都是使用HashTable, Map,Dictionary 或者别的工具。

    ShenduCC
  • Golang Leetcode 450. Delete Node in a BST.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175007

    anakinsun
  • python中创建和遍历二叉树

    py3study

扫码关注云+社区

领取腾讯云代金券