236. Lowest Common Ancestor of a Binary Tree
236. Lowest Common Ancestor of a Binary Tree
题目
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:
![](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png)
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:
![](https://assets.leetcode.com/uploads/2018/12/14/binarytree.png)
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, 105]
. -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
的最低共同祖先。
递归法的优点在于其简洁性和直观性,但需要注意避免重复计算,以提高性能。
代码
/**
* @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. 二叉搜索树的最近公共祖先
- 1644. 二叉树的最近公共祖先 II
- 1650. 二叉树的最近公共祖先 III
- 1676. 二叉树的最近公共祖先 IV
- 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
- 剑指 Offer 68 - II. 二叉树的最近公共祖先
- 🔒 Smallest Common Region
- 2225. 找出输掉零场或一场比赛的玩家
- 🔒 Lowest Common Ancestor of a Binary Tree II
- 🔒 Lowest Common Ancestor of a Binary Tree III
- 🔒 Lowest Common Ancestor of a Binary Tree IV
- 2096. 从二叉树一个节点到另一个节点每一步的方向
- 2509. 查询树中环的长度
- [235. 二叉搜索树的最近公共祖先](./0235.md)
- [1644. 二叉树的最近公共祖先 II](./1644.md)
- [1650. 二叉树的最近公共祖先 III](./1650.md)
- [1676. 二叉树的最近公共祖先 IV](./1676.md)
- [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](./jz_offer_68_1.md)
- [剑指 Offer 68 - II. 二叉树的最近公共祖先](./jz_offer_68_2.md)
- [🔒 Smallest Common Region](https://leetcode.com/problems/smallest-common-region)
- [2225. 找出输掉零场或一场比赛的玩家](https://leetcode.com/problems/find-players-with-zero-or-one-losses)
- [🔒 Lowest Common Ancestor of a Binary Tree II](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii)
- [🔒 Lowest Common Ancestor of a Binary Tree III](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii)
- [🔒 Lowest Common Ancestor of a Binary Tree IV](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv)
- [2096. 从二叉树一个节点到另一个节点每一步的方向](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another)
- [2509. 查询树中环的长度](https://leetcode.com/problems/cycle-length-queries-in-a-tree)