# 236. Lowest Common Ancestor of a Binary Tree

## 1.問題 

* 給予一個binary tree, 找出Lowest Common Ancestor (LCA)

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHT4URR-Uo1ttjHGe6J%2F-LHT57DC1tyAMXxUM_j8%2F2018071507.jpg?alt=media\&token=37241b81-de30-4793-b8e7-b61fbeff0555)

## 2.想法 

* 這題與[235. Lowest Common Ancestor of a Binary Search Tree](https://jenhsuan.gitbooks.io/letcode/content/leetcode235-lowest-common-ancestor-of-a-binary-search-tree.html)類似, 但差別在於235是在BST上面搜尋, 可以利用BST的特性來撰寫演算法, 但這題少了這個特性可以使用, 因此需要不同的算法
* 可以使用DFS
  * 每次函式會呼叫自己並將root的左右子代當成新的root(新的左右函式), 目的是搜尋p, q
  * 當函式中的root等於p, q時, 代表搜尋到了, 並開始return
  * 當新的左右函式皆有回傳值時, 該次的root即為所求

## 3.程式碼 

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL)
        {
            return NULL;
        }
        
        if (root == p || root == q)
        {
            return root;
        }
        
        TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
        
        if (leftLCA != NULL && rightLCA != NULL)
        {
            return root;
        }
        
        if (leftLCA != NULL)
        {
            return leftLCA;
        }
        return rightLCA;
        
    }
};
```

```
```

## 4.Performance