# \[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]

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F04be42ec20c54ac04a19406d4962da4ddfac9071.png?generation=1601089831541706\&alt=media)

示例 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)
```