# \[236]\[中等]\[DFS] 二叉搜索树的最近公共祖先

## 题目描述

[236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/) [剑指 Offer 68 - II. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4]

![](/files/-MI7Nsw28CIj1CobA-Xo)

示例 1:

```
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
```

示例 2:

```
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
```

说明:

* 所有节点的值都是唯一的。
* p、q 为不同节点且均存在于给定的二叉树中。

## 解题思路

### 由上向下的思路

在DFS递归的过程中, 判断以当前结点为根节点的树中都有哪些节点, 找到第一个包含`p`和`q`的节点, 就是要找的最近公共祖先节点.

使用哈希表存储每个节点代表的树中包含的所有节点.

```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':
        def dfs(node):
            if node is None:
                return False, set(), None

            node_set = set([node])
            left_status, left_set, parnet = dfs(node.left)
            if left_status:
                return left_status, left_set, parnet
            node_set = node_set.union(left_set)
            if p in node_set and q in node_set:
                return True, node_set, node
            right_status, right_set, parnet = dfs(node.right)
            if right_status:
                return right_status, right_set, parnet
            node_set = node_set.union(right_set)
            if p in node_set and q in node_set:
                return True, node_set, node
            return False, node_set, None

        _, _, p = dfs(root)

        return p
```

### 由下向上的思路

[236. 二叉树的最近公共祖先（后序遍历 DFS ，清晰图解）](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/) [【C++ 经典递归】思路非常好理解 时间复杂度O(n), 空间复杂度O(n)](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/c-jing-dian-di-gui-si-lu-fei-chang-hao-li-jie-shi-/)

构建一个函数, 返回的内容是**候选的最近公共祖先**结点.

首先, 一个节点`root`如果是`p`和`q`的最近公共祖先, 则只可能是以下几种情况:

* `p`和`q`分别在`root`的左右子树中, 不能在同一侧子树中
* `p = root`, 且`q`在`root`的任一子树中
* `q = root`, 且`p`在`root`的任一子树中

因此, DFS使用的递归函数在遇到`p`或`q`时, 就无需继续向下遍历, 可以开始向上回溯了. 因为节点`p`或`q`满足上面的第二, 第三条, 如果真实情况就是`q`在`p`为根节点的子树中, 或反过来, 那么这个节点就是最近公共祖先节点.

在回溯的过程中, 根据左子树`left`和右子树`right`的返回, 有四种情况:

* `left`和`right`同时为`None`, 说明`root`的左右子树都不包含`p`和`q`, 继续向上返回`None`
* `left`和`right`都不为空, 说明`p`和`q`分别在`root`的不同侧, 因此`root`是最近公共祖先节点, 返回`root`
* `left`为空, `right`不为空, 直接返回`right`
  * 可能是`right`中只有`p`, 没有`q`(或只有`q`), 此时的`right`是指向`p`为根节点的
  * 可能`right`中包含`p`和`q`节点, 此时的`right`是指向最近公共祖先节点的
* `left`不为空, `right`为空, 返回`left`, 具体情况同第三种情况

还有一个边际情况是遇到了空节点, 直接返回`None`就可以.

```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:
        def dfs(node):
            if not node or node is p or node is q:
                return node

            left = dfs(node.left)
            right = dfs(node.right)
            if not left:
                return right
            if not right:
                return left
            return node
        return dfs(root)
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/shu/236-er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian.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.