# 在二叉树中找到两个节点的最近公共祖先
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#中等) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#二叉树树)
> [在二叉树中找到两个节点的最近公共祖先\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116)
**问题简述**
```
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
```
**思路1：树形DP（后序遍历）**
* 考虑判断结点 x 是否为 o1 和 o2 的最近公共祖先需要从左右子节点获取哪些信息；
* `has_o1`：是否存在 o1
* `has_o2`：是否存在 o2
* `ret`：是否已经找到最近公共祖先
* 然后根据子节点的以上信息，生成当前节点的这些信息，并返回；
* 详见代码；
Python
```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
```
**思路2：路径对比（后序遍历）**
* 记录从 o1 和 o2 到根节点的路径，找到两个路径上最后一个相同的节点；
* 因为是后序遍历，为了顺序比较所有祖先，可以考虑使用队列头插来保存节点；
Python
```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
```
---
# 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://imhuay.gitbook.io/studies/algorithms/problems/2022/04/niu-ke-0102-zhong-deng-zai-er-cha-shu-zhong-zhao-dao-liang-ge-jie-dian-de-zui-jin-gong-gong-zu-xian.md?ask=
```
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.