https://leetcode.com/problems/delete-node-in-a-bst
此方法有誤，因為指定 null 不會真的刪除，要用下一個方法
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
def search(node, target):
if not node or node.val == target:
return node
if target > node.val:
return search(node.left, target)
else:
return search(node.right, target)
def findLargest(node):
if not node or not node.right:
return node
return findLargest(node.right)
def findSmallest(node):
if not node or not node.left:
return node
return findSmallest(node.left)
# find node to delete
node = search(root, key)
if not node:
return root
# if node is leaf, delete it
if node.left == None and node.right == None:
node = None
# else, find largest of left subtree or smallest of right subtree, replact with it
else:
if node.right:
right_smallest = findSmallest(node.right)
node.val = right_smallest.val
right_smallest = None
else:
left_largest = findLargest(node.left)
node.val = left_largest.val
left_largest = None
return root
正確方法
# Definition for a binary tree node.
# 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
# 如果要刪除的 node 不是 leaf，要馬把左邊最大換成 node，要馬右邊最小，這裡只實作其中一種
def findLargest(node):
while node.right:
node = node.right
return node
# 這個 functuin 會回傳刪除後
def delete(node, target):
# 如果遞迴到 leaf 都沒有找到，回傳 null
if not node:
return node
# 如果目標值比當前 node 小，往左邊找，左邊的點要變成刪除後的新 subtree
if target < node.val:
node.left = delete(node.left, target)
# 如果目標值比當前 node 大，往右邊找，右邊的點要變成刪除後的新 subtree
elif target > node.val:
node.right = delete(node.right, target)
# 如果找到了
else:
# 如果只有右邊，直接把右邊接進來
if not node.left:
return node.right
# 如果只有左邊，直接把左邊接進來
elif not node.right:
return node.left
# 如果有左也有右，先找出左邊最大的值，更新當前 node，然後把最大的那個刪了
temp = findLargest(node.left)
node.val = temp.val
node.left = delete(node.left, temp.val)
return node
return delete(root, key)
TC: O(n) 走訪整顆樹找到要刪除的點，刪除也是 O(n)，總體也是 O(n)
SC: O(H) 遞迴深度為樹高，如果是平衡二元樹，則為 O(log(n))
自己想過一遍
# Definition for a binary tree node.
# 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
def findLargest(node):
while node.right:
node = node.right
return node
def delete(node, target):
# in leaf, not found
if not node:
return node
# node.right will attach to a new subtree
if target > node.val:
node.right = delete(node.right, target)
# node.left will attach to a new subtree
elif target < node.val:
node.left = delete(node.left, target)
# found
else:
# case: target is in leaf
if not node.left and not node.right:
return None
# case: not leaf, only right
elif not node.left:# Definition for a binary tree node.
# 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
def findLargest(node):
while node.right:
node = node.right
return node
def delete(node, target):
# in leaf, not found
if not node:
return node
# node.right will attach to a new subtree
if target > node.val:
node.right = delete(node.right, target)
# node.left will attach to a new subtree
elif target < node.val:
node.left = delete(node.left, target)
# found
else:
# case: target is in leaf
if not node.left and not node.right:
return None
# case: not leaf, only right
elif not node.left:
return node.right
# case: not leaf, only left
elif not node.right:
return node.left
# case: not leaf, with left and right
else:
left_largest = findLargest(node.left)
node.val = left_largest.val
node.left = delete(node.left, left_largest.val)
return node
return delete(root, key)
return node.right
# case: not leaf, only left
elif not node.right:
return node.left
# case: not leaf, with left and right
else:
left_largest = findLargest(node.left)
node.val = left_largest.val
node.left = delete(node.left, left_largest.val)
return node
return delete(root, key)