###### tags: `Leetcode` `medium` `tree` `dfs` `python` `c++` `Top 100 Liked Questions`

# 236. Lowest Common Ancestor of a Binary Tree

## [題目連結:] https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

## 題目:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes ```p``` and ```q``` as the lowest node in T that has both ```p``` and ```q``` as descendants (where we allow **a node to be a descendant of itself**).”


## 解題想法:
* 此題為求兩node之祖先
* 兩node一定存在
* 所有node值皆不同
* 自己可視為自己的祖先

* 遞迴求解
* 初始判斷:
* 若root空: return None
* 若(root == p ) or ( root == q ):
* return root
* 遞迴:
* left=遞迴左子判斷
* right=遞迴右子判斷
* 若left與right皆存在
* 表示該root即為祖先
* 否則回傳left or right非空的一方

## Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root==p or root==q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        #若在該root左右子樹分別可找到left right 
        if left and right:
            #則該root即為祖先
            return root
        #在同一子樹  
        return left if left else right

## C++:

/**
 * 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==nullptr)
            return nullptr;
        if (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;
        return (left!=nullptr)? left:right;
    }
};