新知一下
海量新知
5 9 7 6 0 4 3

​LeetCode刷题实战450:删除二叉搜索树中的节点

程序IT圈 | 程序员编程技术 2021/11/26 15:09

今天和大家聊的问题叫做 删除二叉搜索树中的节点 ,我们先来看题面:

https://leetcode-cn.com/problems/delete-node-in-a-bst/

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.

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

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

首先找到需要删除的节点;

如果找到了,删除它。

示例

新知达人, ​LeetCode刷题实战450:删除二叉搜索树中的节点

新知达人, ​LeetCode刷题实战450:删除二叉搜索树中的节点

解题

https://blog.csdn.net/xxx_gt/article/details/103673563

首先是利用一个递归函数,每次排除1/2子树的节点,跟我上面的中序遍历相比,大大提高了效率。

递归函数,有两个要点要理解,一个是递归函数的作用,二是它返回的结果是什么。这道题里,这个递归函数的作用就是 删除一棵树里的目标节点,返回的是这棵修改后的树的根节点root。

递归过程:

deleteNode(root, key)

如果根节点的值大于目标节点key的值,说明key在左子树,所以递归调用(root.left, key)。key在左子树,也就说明 只用修改左子树就行了,右子树不用动,所以可以使 root.left = deleteNode(root.left, key).

如果根节点的值小于目标节点key的值,说明key在右子树,所以递归调用(root.right, key)。同理,rot.rght = deleteNode(root.right, key).

如果根节点的值等于目标节点key的值,说明找到key了,开始进行下一步处理。

(启示:说到 二叉搜索树BST时,不仅要想到中序遍历的结果是排好序的,还要想到可以递归,有点像二分查找的模式寻找目标值,提高效率)

删除节点:

经过上一步的递归过程,找到了key,而且key是要调整的这个子树的根节点。

(思考1:竟然不用存储pre节点,是怎么做到连接两个部分的树的?)

当遍历到这个节点时,其实变量名只是起到一个指针的作用,直接修改它的值就行,直接令它的值等于它的继承节点的值。

调整子树:

这部分用到两个子函数:

def successor(root): # 代表中序遍历序列的后一个节点,即比当前节点大的最小节点

root = root.right

while root.left:

root = root.left

return root.val

def predecessor(root): # 代表中序遍历序列的前一个节点,即比当前节点小的最大节点

root = root.left

while root.right:

root = root.right

return root.val

要分三种情况:

整个子树就只有一个节点,也就是根节点是叶节点,这是直接令其等于None就行了。

根节点有右子树,继承节点就选择 它的后一个节点(比目标节点大的最小节点)。

root.val = successor(root) # 用它的后继节点代替它

root.right = self.deleteNode(root.right, root.val) # 修改右子树

根节点无右子树但有左子树,继承节点就选择 它的前一个节点(比目标节点小的最大节点)。

root.val = predecessor(root) # 用它的后继节点代替它

root.left= self.deleteNode(root.left, root.val) # 修改右子树

代码如下:

class Solution:

    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:

        if not root:

            return None

        def successor(root): # 代表中序遍历序列的下一个节点,即比当前节点大的最小节点

            root = root.right

            while root.left:

                root = root.left

            return root.val

        

        def predecessor(root):

            root = root.left

            while root.right:

                root = root.right

            return root.val

        

        if key > root.val: # 如果key大于根节点,则从右子树寻找

            root.right = self.deleteNode(root.right, key)

        elif key < root.val: # 如果key小于根节点,则从左子树寻找

            root.left = self.deleteNode(root.left, key)

        else: # key == 根节点

            if not root.left and not root.right: # 如果根节点是叶节点,则直接删除该节点

                return  None

            if root.right: # 如果该节点有右节点,则要找比它大的下一个节点(后继节点)

                root.val = successor(root) # 用它的后继节点代替它

                root.right = self.deleteNode(root.right, root.val)

            else:

                root.val = predecessor(root)

                root.left = self.deleteNode(root.left, root.val)

        return root


更多“算法”相关内容

更多“算法”相关内容

新知精选

更多新知精选