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

0450. 删除二叉搜索树中的节点 #

  • 标签:树
  • 难度:中等

题目大意 #

给定一个二叉搜索树的根节点 root,以及一个值 key。要求从二叉搜索树中删除 key 对应的节点。并保证删除后的树仍是二叉搜索树。要求算法时间复杂度为 0(h),h 为树的高度。返回二叉搜索树的根节点。

解题思路 #

删除分两个步骤:查找和删除。查找通过递归查找,删除的话需要考虑情况。

递归,遍历搜索二叉树。对于当前节点:

  • 如果节点为空,返回当前节点。
  • 如果当前节点值大于 key,则去左子树中搜索并删除,此时 root.left 也要跟着递归更新。
  • 如果当前节点值小于 key,则去右子树中搜索并删除,此时 root.right 也要跟着递归更新。
  • 如果当前节点值等于 key,则该节点就是待删除节点。
    • 如果当前节点的左子树为空,则删除该节点之后,则右子树代替当前节点位置,返回右子树。
    • 如果当前节点的右子树为空,则删除该节点之后,则左子树代替当前节点位置,返回左子树。
    • 如果当前节点的左右子树都有,则将左子树转移到右子树最左侧的叶子节点位置上,然后右子树代替当前节点位置。

第三种情况如下所示:

1
2
3
4
5
6
删除 4 之前:
      4
    /   \  
  2       6
 / \     / \
1   3   5   7
1
2
3
4
5
6
7
8
删除 4 之后:    
      6
     / \  
    5   7
   /      
  2   
 / \     
1   3

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root

        if root.val > key:
            root.left = self.deleteNode(root.left, key)
            return root
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
            return root
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                curr = root.right
                while curr.left:
                    curr = curr.left
                curr.left = root.left
                return root.right
本站总访问量  次  |  您是本站第  位访问者