-
Notifications
You must be signed in to change notification settings - Fork 0
/
delete-node-in-a-bst_450.py
64 lines (47 loc) · 1.8 KB
/
delete-node-in-a-bst_450.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 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.
# Example 1:
# 
# Input: root = [5,3,6,2,4,null,7], key = 3
# Output: [5,4,6,2,null,null,7]
# Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
# One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
# Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
# 
# Example 2:
# Input: root = [5,3,6,2,4,null,7], key = 0
# Output: [5,3,6,2,4,null,7]
# Explanation: The tree does not contain a node with value = 0.
# Example 3:
# Input: root = [], key = 0
# Output: []
# ---------------------------------------Runtime 74 ms Beats 47.14% Memory 20.8 MB Beats 49.73%---------------------------------------
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def deleteNode(
self, root: Optional[TreeNode], key: int
) -> Optional[TreeNode]:
if not root:
return root
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
cur = root.right
while cur.left:
cur = cur.left
root.val = cur.val
root.right = self.deleteNode(root.right, root.val)
return root