Leetcode 450. Delete Node in a BST

Wanda ·

更新时间:2024-11-15

· 966 次阅读

一：题意：

删除一颗二叉搜索树的一个节点。

二：思路

二叉搜索树的结点删除比插入较为复杂，总体来说，结点的删除可归结为三种情况：

1、如果结点z没有孩子节点，那么只需简单地将其删除，并修改父节点，用NIL来替换z； 2、如果结点z只有一个孩子，那么将这个孩子节点提升到z的位置，并修改z的父节点，用z的孩子替换z； 3、如果结点z有2个孩子，那么查找z的后继y，此外后继一定在z的右子树中，然后让y替换z。 python实现

class Solution(object):
    def deleteNode(self, root, key):
        def postOrder(root):  # 后序遍历
            if not root: return root
            # 后序遍历
            if key  root.val:
                root.right = postOrder(root.right)
            else: # 找到需要删的节点了
                if not root.left:  # 没有左儿子，直接删除root, 返回右儿子
                    return root.right
                if not root.right: # 没有右儿子
                    return root.left
                parent = root       # 既有左儿子也有右儿子
                last = root.right
                while last.left:  # 找到root的右子树的最左边的那个叶子节点
                    parent = last
                    last = last.left
                root.val = last.val  # 用右子树的最左边的叶子节点的值替换root
                if parent != root:
                    parent.left = last.right
                else:
                    parent.right = last.right
            return root
        res = postOrder(root)
        return res

作者：rain_Man2018

leetcode IN bst node delete

1024 个赞