# 在二叉树中找到两个节点的最近公共祖先

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E4%BA%8C%E5%8F%89%E6%A0%91/%E6%A0%91\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#二叉树树)

> [在二叉树中找到两个节点的最近公共祖先\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116)

**问题简述**

```
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
```

**思路1：树形DP（后序遍历）**

* 考虑判断结点 x 是否为 o1 和 o2 的最近公共祖先需要从左右子节点获取哪些信息；
  * `has_o1`：是否存在 o1
  * `has_o2`：是否存在 o2
  * `ret`：是否已经找到最近公共祖先
* 然后根据子节点的以上信息，生成当前节点的这些信息，并返回；
* 详见代码；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        
        from dataclasses import dataclass
        
        @dataclass
        class Info:
            has_o1: bool  # 以当前结点为根节点的树中是否存在 o1
            has_o2: bool  # 以当前结点为根节点的树中是否存在 o2
            ret: int  # o1 和 o2 的最近公共祖先

        def dfs(x):
            if not x: return Info(False, False, None)
            
            l, r = dfs(x.left), dfs(x.right)
            has_o1 = l.has_o1 or r.has_o1 or x.val == o1
            has_o2 = l.has_o2 or r.has_o2 or x.val == o2
            ret = l.ret or r.ret or x.val if has_o1 and has_o2 else None
            return Info(has_o1, has_o2, ret)
        
        return dfs(root).ret
```

</details>

**思路2：路径对比（后序遍历）**

* 记录从 o1 和 o2 到根节点的路径，找到两个路径上最后一个相同的节点；
* 因为是后序遍历，为了顺序比较所有祖先，可以考虑使用队列头插来保存节点；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        
        def dfs(x, o, path):  # 获取 o 的祖先路径
            if not x: return False
            l, r = dfs(x.left, o, path), dfs(x.right, o, path)
            if l or r or x.val == o: 
                path.appendleft(x.val)
                return True
            return False
        
        from collections import deque
        p1 = deque(); dfs(root, o1, p1)
        p2 = deque(); dfs(root, o2, p2)
        
        pre = -1
        for v1, v2 in zip(p1, p2):
            if v1 == v2: pre = v1
            else: break
                
        return pre
```

</details>
