LEETCODE 450. 删除二叉搜索树中的节点

LEETCODE 450. 删除二叉搜索树中的节点

题目描述

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

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

首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。

示例:

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

题目地址
中文版
英文版

代码实现

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return root
        if root.val==key:
            if not root.left and not root.right:
                return None
            elif not root.left and root.right:
                return root.right
            elif root.left and not root.right:
                return root.left
            head = root.right
            p = head
            while p.left:
                p = p.left
            p.left = root.left
            return head
        d = dict()
        p = root
        node = None
        while p:
            if p.val>key and p.left:
                d[p.left] = p
                p = p.left
            elif p.val<key and p.right:
                d[p.right] = p
                p = p.right
            else:
                node = p
                break
        if not node:
            return root
        if node.val!=key:
            return root
        parent = d[node]
        #print "pareint->"+str(parent.val)
        #print "node->"+str(node.val)
        if node.left and node.right:
            print ""
            p = node.right
            while p.left:
                p = p.left
            p.left = node.left
            if parent.left==node:
                parent.left=node.right
            else:
                parent.right=node.right
        elif node.left and not node.right:
            print node.left.val
            if parent.left==node:
                parent.left=node.left
            else:
                parent.right=node.left
        elif not node.left and node.right:
            if parent.left==node:
                parent.left=node.right
            else:
                parent.right=node.right
        else:
            if parent.left==node:
                parent.left=None
            else:
                parent.right=None
        return root
                                                        
0 次阅读

发表评论

电子邮件地址不会被公开。