? ? ? ?

????????在樹結構中，祖先指的是一個節點的父節點或更高層級的父節點。公共祖先是指同時為節點p和q的祖先的節點。最近公共祖先（LCA）則是指在所有公共祖先中，距離p和q最近的那個節點。尋找LCA的方法可以按以下情況進行分析：

1. 當前節點為空節點
2. 當前節點就是p節點
3. 當前節點就是q節點
4. 當前節點既不是p也不是q，且p和q位于其子樹中：
   • p和q分別位于左右子樹
   • p和q都在左子樹
   • p和q都在右子樹
   • p和q都不在子樹中

具體解決方案如下：

情況1：空節點不可能是p和q的LCA。

情況2和3：如果當前節點是p或q，直接返回當前節點。因為若當前節點是p，而q是其子節點，則p就是LCA（節點可以是自身的LCA）。若q不在p的子樹中，則無需繼續在p的子樹中搜索。

情況4.1：當前節點就是LCA。因為如果LCA在左子樹，則不會是q的祖先；在右子樹則不會是p的祖先；在上層節點則不滿足"最近"的條件。

情況4.2：LCA必定在左子樹中，因此遞歸搜索左子樹。

情況4.3和4.4可以合并處理：若p和q都在右子樹，則遞歸搜索右子樹；若都不在子樹中，則右子樹也為空。? ? ? ??

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root || root == p || root == q) {return root;}TreeNode *left = lowestCommonAncestor(root->left,p,q);TreeNode *right = lowestCommonAncestor(root->right,p,q);if (left && right) {return root;}if (left) {return left;}return right;}
};

? ? ? ? 時間復雜度：O(n),n為節點個數

? ? ? ? 空間復雜度：O(n)

類似的可以求解一下235. 二叉搜索樹的最近公共祖先 - 力扣（LeetCode）