450. 刪除二叉搜尋樹中的節點

摘要： 450. 刪除二叉搜尋樹中的節點 題意 給定一個二叉搜尋樹的根節點 root 和一個值 ...

450. 刪除二叉搜尋樹中的節點

題意

給定一個二叉搜尋樹的根節點 root 和一個值 key ，刪除二叉搜尋樹中的 key 對應的節點，並保證二叉搜尋樹的性質不變。返回二叉搜尋樹（有可能被更新）的根節點的引用。

一般來說，刪除節點可分為兩個步驟：

1. 首先找到需要刪除的節點；

2. 如果找到了，刪除它。

說明： 要求演算法時間複雜度為 O(h)，h 為樹的高度。

解題思路

• 找到要刪除的結點以後，將該結點的值替換成左子樹中的最右子結點的值，並且將替換後的結點刪除；

• 和上面類似，只不過是被右子樹中的最左子結點替換；

實現

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:
root.left = self.deleteNode(root.left, key)
# 從右子樹中找
elif root.val < key:
root.right = self.deleteNode(root.right, key)
else:
# 判斷是否左右子樹是否都存在
if not root.left:
return root.right
elif not root.right:
return root.left
else:
# 找到左子樹的最右子結點
tmp = root.left
while tmp.right:
tmp = tmp.right
root.val = tmp.val
# 刪除左子樹的最右子結點後，重構左子樹
root.left = self.deleteNode(root.left, tmp.val)
return root

def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: 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
​
if not root.left:
return root.right
elif not root.right:
return root.left

tmp = self.findmin(root.right)
tmp.right = self.delmin(root.right)
tmp.left = root.left
return tmp

def findmin(self, root):
"""
找到右子樹中的最左子結點
"""
if not root.left:
return root
return self.findmin(root.left)

def delmin(self, root):
"""
刪除右子樹中的最左子結點
"""
if not root.left:
return root.right

root.left = self.delmin(root.left)
return root