題目
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
用例
示例 1：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節點 5 和節點 1 的最近公共祖先是節點 3 。
示例 2：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節點 5 和節點 4 的最近公共祖先是節點 5 。因為根據定義最近公共祖先節點可以為節點本身。
示例 3：
輸入：root = [1,2], p = 1, q = 2
輸出：1
提示：
樹中節點數目在範圍 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于給定的二叉樹中。
思路
求最近公共祖先，隻存在兩種情況：1是其中一點是另一節點的祖先，2是兩點各分布在目标答案的兩顆子樹之中
是以我們對樹進行後序周遊，尋找左右兩棵子樹中都存在p或q的節點即為目标節點
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr||root==p||root==q)return root;//隐藏了一個條件 如果目前節點找到 另一個節點存在其子樹中，直接傳回目前節點
TreeNode*left=lowestCommonAncestor(root->left,p,q);
TreeNode*right=lowestCommonAncestor(root->right,p,q);
if(left==nullptr)//左邊沒找到 說明右邊可能找到，右邊也沒找到情況下傳回nullptr
return right;
if(right==nullptr)//同理
return left;
return root;//兩邊都找到 傳回目前節點
}
};