236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
🟠 🔖 树
深度优先搜索
二叉树
🔗 力扣
LeetCode
题目
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p
and q
as the lowest node in T
that has both p
and q
as descendants (where we allow a node to be a descendant of itself )."
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 10^5]
. -10^9 <= Node.val <= 10^9
- All
Node.val
are unique. p != q
p
andq
will exist in the tree.
题目大意
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
维基百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
解题思路
这是一道经典的题目,寻找任意一个二叉树中两个结点的 LCA 最近公共祖先,考察递归。
从根节点开始,递归地向左子树和右子树搜索。递归的终止条件有几种情况:
- 如果当前节点为
null
,表示遍历到空节点,直接返回null
。 - 如果当前节点等于
p
或q
,表示找到了其中一个节点,直接返回当前节点。
递归步骤如下:
- 递归地在左子树中寻找
p
和q
的最低共同祖先,结果存储在变量left
中。 - 递归地在右子树中寻找
p
和q
的最低共同祖先,结果存储在变量right
中。
然后,根据 left
和 right
的情况,可以得出以下结论:
- 如果
left
和right
都不为null
,说明p
和q
分别位于当前节点的左右子树,因此当前节点就是它们的最低共同祖先,直接返回当前节点。 - 如果只有
left
不为null
,说明p
和q
都在左子树,最低共同祖先在左子树中,返回left
。 - 如果只有
right
不为null
,说明p
和q
都在右子树,最低共同祖先在右子树中,返回right
。
递归法的关键在于将大问题划分为规模较小的子问题,然后通过递归调用来解决子问题,最终得到整体的解决方案。在这里,递归调用的子问题是在左右子树中寻找 p
和 q
的最低共同祖先。
递归法的优点在于其简洁性和直观性,但需要注意避免重复计算,以提高性能。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是树中节点的总数,因为在最坏的情况下,需要检查每个节点来找到最近公共祖先。 - 空间复杂度:
O(h)
,其中h
是树的高度,空间复杂度主要由递归调用栈的深度决定。- 在平衡树中,递归深度为
O(h)
,其中h
是树的高度。 - 在最坏情况下(例如,树是完全不平衡的),递归的深度可以达到
O(n)
,其中n
是树中节点的总数。
- 在平衡树中,递归深度为
代码
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (!root || root == p || root == q) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left ? left : right;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
235 | 二叉搜索树的最近公共祖先 | [✓] | 树 深度优先搜索 二叉搜索树 1+ | |
1257 | 最小公共区域 🔒 | 树 深度优先搜索 广度优先搜索 3+ | ||
1644 | 二叉树的最近公共祖先 II 🔒 | 树 深度优先搜索 二叉树 | ||
1650 | 二叉树的最近公共祖先 III 🔒 | 树 哈希表 双指针 1+ | ||
1676 | 二叉树的最近公共祖先 IV 🔒 | 树 深度优先搜索 哈希表 1+ | ||
2096 | 从二叉树一个节点到另一个节点每一步的方向 | 树 深度优先搜索 字符串 1+ | ||
2225 | 找出输掉零场或一场比赛的玩家 | 数组 哈希表 计数 1+ | ||
2509 | 查询树中环的长度 | 树 数组 二叉树 |