Skip to content

450 Delete Node in a BST

450. Delete Node in a BST

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

难度 : Medium

思路:

从二叉搜索树中删除节点x的方法如下:

• 如果x没有子节点,或者只有一个孩子,直接将x“切下”;

• 否则,x有两个孩子,我们用其右子树中的最小值替换掉x,然后将右子树中的这一最小值递归的“切掉”。

AC代码

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        def findmin(root):
            while root.left:
                root = root.left
            return root


        if not root : return None
        elif key < root.val: root.left = self.deleteNode(root.left, key)
        elif key > root.val : root.right = self.deleteNode(root.right, key)
        else:
            if root.left and root.right:
                tmp = findmin(root.right)
                root.val = tmp.val
                root.right = self.deleteNode(root.right, tmp.val)
            else:
                if not root.left:
                    root = root.right
                elif not root.right:
                    root = root.left
        return root

其实这个代码还是需要花点时间来理解,需要画个图,理解这个root是每个stack return回去然后被接在原来的树上的,if 这个node并不是在node左右。



回到顶部