# 236. Lowest Common Ancestor of a Binary Tree

## 1.問題 

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

![](/files/-LHT57DC1tyAMXxUM_j8)

## 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/236.-lowest-common-ancestor-of-a-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.