0236. 二叉树的最近公共祖先 #
- 标签:树
- 难度:中等
题目大意 #
描述:给定一个二叉树的根节点 root
,以及二叉树中两个节点 p
和 q
。
要求:找到该二叉树中指定节点 p
、q
的最近公共祖先。
说明:
- 祖先:如果节点
p
在节点node
的左子树或右子树中,或者p == node
,则称node
是p
的祖先。 - 最近公共祖先:对于树的两个节点
p
、q
,最近公共祖先表示为一个节点lca_node
,满足lca_node
是p
、q
的祖先且lca_node
的深度尽可能大(一个节点也可以是自己的祖先)。 - 树中节点数目在范围 $[2, 10^5]$ 内。
- $-10^9 \le Node.val \le 10^9$。
- 所有
Node.val
互不相同。 p != q
。p
和q
均存在于给定的二叉树中。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
设 lca_node
为节点 p
、q
的最近公共祖先。则 lca_node
只能是下面几种情况:
p
、q
在lca_node
的子树中,且分别在lca_node
的两侧子树中。p == lca_node
,且q
在lca_node
的左子树或右子树中。q == lca_node
,且p
在lca_node
的左子树或右子树中。
下面递归求解 lca_node
。递归需要满足以下条件:
- 如果
p
、q
都不为空,则返回p
、q
的公共祖先。 - 如果
p
、q
只有一个存在,则返回存在的一个。 - 如果
p
、q
都不存在,则返回None
。
具体思路为:
- 如果当前节点
node
等于p
或者q
,那么node
就是p
、q
的最近公共祖先,直接返回node
。 - 如果当前节点
node
不为None
,则递归遍历左子树、右子树,并判断左右子树结果。- 如果左右子树都不为空,则说明
p
、q
在当前根节点的两侧,当前根节点就是他们的最近公共祖先。 - 如果左子树为空,则返回右子树。
- 如果右子树为空,则返回左子树。
- 如果左右子树都为空,则返回
None
。
- 如果左右子树都不为空,则说明
- 如果当前节点
node
为None
,则说明p
、q
不在node
的子树中,不可能为公共祖先,直接返回None
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。