# 236. Lowest Common Ancestor of a Binary Tree

{% embed url="<https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/>" %}

分情况讨论后就容易看出是 recursive traversal:

1. each of p, q in one subtree -> root is the LCA
2. p, q in one subtree:
   * p, q in one continuously line -> case 3&#x20;
   * p, q in separate subtrees -> case 1&#x20;
3. p/q is the root: root is the LCA

> If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is None.

其实就是找到`p, q` 的任何一个就返回它，如果有某个节点的左右子节点分别返回`p, q` ，那说明它肯定就是LCA，如果一直没有这个节点，那说明LCA就是`p, q` 中的一个，那按照这个规则返回到根节点就行。

{% tabs %}
{% tab title="bottom-up" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. each of p, q in one subtree -> root is the LCA
        # 2. p, q in one subtree
        ## 2.1 p, q in one continuously line -> 3 -> certain root returned
        ## 2.2 p, q in separate subtrees -> 1 -> certain root returned
        # 3. p/q is the root: root is the LCA
        if not root or root == q or root == p:
            return root
        # 3 solved, only 1 or 2 now
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r: # case 1
            return root
        else:
            return l if l else r
```

{% endtab %}
{% endtabs %}
