一、二叉搜索樹的最近公共祖先（Leetcode 235）
由于是二叉搜索樹，節點的值有嚴格的順序關系：左子樹的節點值都小于父節點，右子樹的節點值都大于父節點。利用這一點，可以在樹中更高效地找到最低公共祖先。
class Solution:def traversal(self, cur, p, q):# 遞歸的基本情況：當前節點為空，返回 Noneif cur is None:return cur# 如果當前節點的值大于 p 和 q 的值，說明 p 和 q 都在左子樹中if cur.val > p.val and cur.val > q.val: # 左left = self.traversal(cur.left, p, q) # 在左子樹中遞歸查找if left is not None:return left # 如果左子樹中找到了節點，返回該節點# 如果當前節點的值小于 p 和 q 的值，說明 p 和 q 都在右子樹中if cur.val < p.val and cur.val < q.val: # 右right = self.traversal(cur.right, p, q) # 在右子樹中遞歸查找if right is not None:return right # 如果右子樹中找到了節點，返回該節點# 如果左右子樹都不為空，說明 p 和 q 分別在左右子樹中return cur # 返回當前節點，因為當前節點就是它們的最低公共祖先def lowestCommonAncestor(self, root, p, q):return self.traversal(root, p, q) # 從根節點開始查找 p 和 q 的最低公共祖先
二、二叉搜索樹中的插入操作（Leetcode 701）
如果要插入的值小于當前節點的值，應該插入到左子樹；如果要插入的值大于當前節點的值，應該插入到右子樹。
class Solution:# 插入值 val 到二叉搜索樹中def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 如果當前節點為空，創建一個新的節點并返回if root is None or root.val == val:return TreeNode(val) # 創建一個新的 TreeNode 節點，包含插入的值# 如果當前節點值大于 val，則應該將 val 插入到左子樹elif root.val > val:# 如果左子樹為空，直接插入該值作為左子節點if root.left is None:root.left = TreeNode(val) # 創建一個新的節點，并賦值給左子節點else:# 如果左子樹不為空，遞歸地在左子樹中插入 valself.insertIntoBST(root.left, val)# 如果當前節點值小于 val，則應該將 val 插入到右子樹elif root.val < val:# 如果右子樹為空，直接插入該值作為右子節點if root.right is None:root.right = TreeNode(val) # 創建一個新的節點，并賦值給右子節點else:# 如果右子樹不為空，遞歸地在右子樹中插入 valself.insertIntoBST(root.right, val)# 返回根節點，確保樹的結構未被破壞return root
三、刪除二叉搜索樹中的節點（Leetcode 450）
刪除節點的三種情況：
1、節點沒有子節點（葉子節點）：如果節點沒有左子樹也沒有右子樹（即葉子節點），直接刪除該節點，返回 None，表示當前節點被刪除。
2、節點只有右子樹：如果節點沒有左子樹（root.left is None），那么可以用右子樹代替當前節點。刪除該節點并返回右子節點，實際上是把右子樹提升為當前節點的子樹。
3、節點只有左子樹：如果節點沒有右子樹（root.right is None），那么可以用左子樹代替當前節點。刪除該節點并返回左子節點，實際上是把左子樹提升為當前節點的子樹。
4、節點有兩個子樹：從當前節點的右子樹開始，遞歸找到右子樹中最左的節點（cur.left is None），該節點就是右子樹中的最小節點。將該最小節點的左子樹指向當前節點的左子樹。
返回右子樹作為新樹的根節點（也就是當前節點被刪除，右子樹的最小節點替代了它的位置）。
class Solution:# 刪除二叉搜索樹中的節點def deleteNode(self, root, key):# 如果當前節點為空，返回空# 表示沒有找到節點或到達樹的末端if root is None:return root# 如果當前節點的值等于要刪除的值if root.val == key:# 如果節點沒有子節點（葉子節點），直接刪除該節點if root.left is None and root.right is None:return None# 如果節點只有右子樹，直接返回右子樹，刪除當前節點elif root.left is None:return root.right# 如果節點只有左子樹，直接返回左子樹，刪除當前節點elif root.right is None:return root.left# 如果節點有兩個子樹，找到右子樹中的最小節點（左子樹的最左節點）else:cur = root.right # 從右子樹開始# 尋找右子樹中最小的節點（左子樹最深的節點）while cur.left is not None:cur = cur.left# 將右子樹最小節點的左子樹指向當前節點的左子樹cur.left = root.left# 返回右子樹作為新的根節點，替代當前節點return root.right# 如果當前節點的值大于要刪除的值，遞歸到左子樹中刪除if root.val > key:root.left = self.deleteNode(root.left, key)# 如果當前節點的值小于要刪除的值，遞歸到右子樹中刪除if root.val < key:root.right = self.deleteNode(root.right, key)# 返回根節點，確保樹的結構未被破壞return root
)
