问答题【571/1593】二叉树的最近公共祖先

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

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

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入： root = [1,2], p = 1, q = 2

输出： 1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val) {
4 *     this.val = val;
5 *     this.left = this.right = null;
6 * }
7 */
8/**
9 * @param {TreeNode} root
10 * @param {TreeNode} p
11 * @param {TreeNode} q
12 * @return {TreeNode}
13 */
14var lowestCommonAncestor = function(root, p, q) {
15    
16};

难度：

2022-12-30 创建

参考答案

题目要点

个人笔记

参考答案：

我们使用递归，当节点为null或者节点等于p或q向上返回此节点。
在结果向上回溯的过程中，要对左右节点的返回值进行判断：
1. 如果左右节点返回的值都不为null（如图中紫色箭头所示），
  预览

复杂度

时间复杂度: O(n)
空间复杂度: O(1)

Code

1
2/**
3 * Definition for a binary tree node.
4 * function TreeNode(val) {
5 *     this.val = val;
6 *     this.left = this.right = null;
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @param {TreeNode} p
12 * @param {TreeNode} q
13 * @return {TreeNode}
14 */
15var lowestCommonAncestor = function (root, p, q) {
16    var travelTree = function (node, p, q) {
17        if (node == null || node == p || node == q) return node;
18        let left = travelTree(node.left, p, q);
19        let right = travelTree(node.right, p, q);
20        if (left && right) {
21            return node;
22        }
23        else if (left && right == null) {
24            return left;
25        } else if (left == null && right) {
26            return right
27        } else {
28            return null
29        }
30    }
31    return travelTree(root, p, q)
32};

最近更新时间：2023-03-12

问答题【571/1593】二叉树的最近公共祖先

复杂度

Code

赞赏支持