# Definition for a binary tree node.
'''
搜索二叉樹，是一個左子樹小于根節點小于右子樹的特殊二叉樹，
'''
# 這道題使用遞回的方法來做，有洗掉的節點有四種情況，
# 1，是葉子節點，沒有孩子，
# 2，有一個左孩子，直接讓左孩子即為就好了，
# 3，有一個右孩子， 直接讓右孩子即為，
# 4，左右孩子都有， 有兩種辦法，
# （1），找到左孩子值最大的節點，左子樹一直向右遍歷，
# （2），找到右孩子值最小的幾點，右子樹一直向左遍歷，
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: TreeNode, key: int) -> TreeNode:
# 如果root為空，直接回傳，
if root is None:
return root
# 先尋找到需要洗掉的節點，
if root.val > key:
root.left = self.deleteNode(root.left,key)
elif root.val < key:
root.right = self.deleteNode(root.right,key)
else:
# 沒有孩子，那么直接洗掉，然后回傳，
if root.left is None and root.right is None:
root = None
return root
# 有左孩子，讓左孩子即為，
elif root.left and root.right is None:
tmp = root.left
root = None
return tmp
# 只有右孩子，讓右孩子即為，
elif root.right and root.left is None:
tmp = root.right
root = None
return tmp
else:
# # 左右孩子都存在，1，尋找右孩子的最小值，
# curr = root.right
# # 右孩子向左遞回，就是右孩子的最小值，
# while curr.left:
# curr = curr.left
# # 讓右孩子的最小值即為，
# root.val = curr.val
# # 洗掉掉那個節點，
# root.right = self.deleteNode(root.right,curr.val)
# 2，尋找左孩子的最大值，
curr = root.left
while curr.right:
curr = curr.right
root.val = curr.val
root.left = self.deleteNode(root.left,curr.val)
return root
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255476.html
標籤：其他