題目
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
一、代碼實現
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil || root == p || root == q {return root}left := lowestCommonAncestor(root.Left, p, q)right := lowestCommonAncestor(root.Right, p, q)if left != nil && right != nil {return root}if left != nil {return left}return right
}
二、算法分析
1. 核心思路
- 后序遍歷：自底向上查找目標節點，通過遞歸返回值傳遞狀態
- 狀態判斷：當某個節點的左右子樹分別包含目標節點時，即為LCA
2. 關鍵步驟
- 遞歸終止：遇到空節點或目標節點立即返回
- 子樹搜索：分別在左右子樹中查找目標節點
- 結果合并：
- 左右子樹均有返回值 → 當前節點為LCA
- 僅單側有返回值 → 繼續向上傳遞該結果
3. 復雜度
| 指標 | 值 | 說明 |
|---|---|---|
| 時間復雜度 | O(n) | 每個節點遍歷一次 |
| 空間復雜度 | O(h) | 遞歸棧空間，h為樹的高度 |
三、圖解示例
四、邊界條件與擴展
1. 特殊場景驗證
- 節點為根節點：返回根節點
- 節點互為祖先：返回層級更高的節點
- 節點不在樹中：返回null（需預先驗證）
2. 多語言實現
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)return root if left and right else left or right
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);return left != null && right != null ? root : left != null ? left : right;}
}
五、總結與擴展
1. 核心創新點
- 狀態傳遞：利用遞歸返回值攜帶子樹搜索信息
- 短路優化：發現目標節點后立即停止子樹搜索
2. 擴展應用
- 多節點LCA：擴展算法處理多個目標節點
- 帶父指針樹：使用哈希表存儲訪問路徑
- 頻繁查詢優化：結合RMQ算法預處理
3. 工程優化
- 迭代實現：用棧模擬后序遍歷
- 路徑記錄：顯式存儲節點訪問路徑
- 輸入驗證：增加節點存在性檢查
