題目簡介
● 235. 二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p省核、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）⌒逭牛”
● 701.二叉搜索樹中的插入操作
給定二叉搜索樹（BST）的根節(jié)點 root 和要插入樹中的值 value ，將值插入二叉搜索樹关带。 返回插入后二叉搜索樹的根節(jié)點侥涵。 輸入數(shù)據(jù) 保證 ，新值和原始二叉搜索樹中的任意節(jié)點值都不同宋雏。
注意芜飘，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可磨总。 你可以返回 任意有效的結果 嗦明。
● 450.刪除二叉搜索樹中的節(jié)點
給定一個二叉搜索樹的根節(jié)點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節(jié)點蚪燕，并保證二叉搜索樹的性質(zhì)不變娶牌。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用。
一般來說馆纳，刪除節(jié)點可分為兩個步驟：
首先找到需要刪除的節(jié)點诗良；
如果找到了，刪除它厕诡。
初見思路
235.想二叉搜索樹的特性累榜，根節(jié)點左側均小于它，根節(jié)點右側均大于它灵嫌。從根節(jié)點向下遍歷壹罚，當節(jié)點p、q分別位于根節(jié)點左右兩側時寿羞，它是二者的最近公共祖先猖凛。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
lca = root
while True:
if p.val < lca.val and q.val < lca.val:
lca = lca.left
elif p.val > lca.val and q.val > lca.val:
lca = lca.right
else:
break
return lca
701.插入一個節(jié)點到BST中，如果值小于當前節(jié)點绪穆，一只向左插入直到作為葉子節(jié)點辨泳；大于當前節(jié)點則向右；如果值等于當前節(jié)點玖院，那么當前節(jié)點值返回;
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
elif val > root.val:
root.right = self.insertIntoBST(root.right, val)
return root
- 這個題目的難點在于刪除的邏輯很隱晦菠红，并沒有刪除值，而是通過賦值的方式實現(xià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, key):
if root is None: # 如果根節(jié)點為空郊酒，直接返回
return root
if root.val == key: # 找到要刪除的節(jié)點
if root.right is None: # 如果右子樹為空遇绞，直接返回左子樹作為新的根節(jié)點
return root.left
cur = root.right
while cur.left: # 找到右子樹中的最左節(jié)點
cur = cur.left
root.val, cur.val = cur.val, root.val
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root
復盤思路
重點難點
BST的刪除還可以再看下键袱，多品，多讀摹闽。
