###### tags: `LeetCode` `Tree` `Medium` `Recursion`
# LeetCode #236 [Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)
### (Medium)
給定一個二元樹, 找到該樹中兩個指定節點的最近公共祖先。

最近公共祖先的定義為：“對於有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

---

if (!root || root == p || root == q) return root;
確保了回傳值只有三種情況, 找到p, 找到q, 都沒找到(nullptr)。

接下來定義TreeNode* left, right, 且這兩個節點只有可能是p, q, nullptr。

若left, right皆存在, 代表一個在左子樹一個在右子樹, 此時共同祖先為根節點;

若left, right一個存在, 一個不存在, 代表兩個節點都在存在的那一邊的子樹, 此時共同祖先就是存在的那個節點(left or right), 因為它先被找到, 代表它會在較上層。

而若left, right皆不存在, 那可能是整個樹裡面都找不到p, q, 此時回傳nullptr。

---

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 nullptr;
        else if(left&&right)return root;
        return left==nullptr?right:left;
    }
};