1123.最深叶节点的最近公共祖先

【LetMeFly】1123.最深叶节点的最近公共祖先

力扣题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

给你一个有根节点 root 的二叉树,返回它 最深的叶节点的最近公共祖先 。

回想一下:

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 深度 为 0,如果某一节点的深度为 d,那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先S 中的每个节点都在以 A 为根节点的子树中,且 A 的深度达到此条件下可能的最大值。

 

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4]
输出:[2,7,4]
解释:我们返回值为 2 的节点,在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意,节点 6、0 和 8 也是叶节点,但是它们的深度是 2 ,而节点 7 和 4 的深度是 3 。

示例 2:

输入:root = [1]
输出:[1]
解释:根节点是树中最深的节点,它是它本身的最近公共祖先。

示例 3:

输入:root = [0,1,3,null,2]
输出:[2]
解释:树中最深的叶节点是 2 ,最近公共祖先是它自己。

 

提示:

  • 树中的节点数将在 [1, 1000] 的范围内。
  • 0 <= Node.val <= 1000
  • 每个节点的值都是 独一无二 的。

 

注意:本题与力扣 865 重复:https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

方法一:深度优先搜索(DFS)

们把最深的叶节点的最近公共祖先,称之为 $\textit{lca}$节点。

编写一个函数dfs(root),返回以root为根的子树的{lca, 深度}

  • 如果左子树更深,则返回{左子的lac, 左子深度 + 1}

  • 如果右子树更深,则返回{右子的lac, 右子深度 + 1}

  • 否则(左右子树深度相同),则返回{root,左子深度 + 1}

  • 时间复杂度$O(n)$,其中$n$为二叉树节点个数

  • 空间复杂度$O(n)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
* @Author: LetMeFly
* @Date: 2023-09-06 22:43:49
* @LastEditors: LetMeFly
* @LastEditTime: 2023-09-06 22:49:44
*/
typedef pair<TreeNode*, int> pti;
class Solution {
private:
pti dfs(TreeNode* root) {
if (!root) {
return {nullptr, 0};
}
pti left = dfs(root->left);
pti right = dfs(root->right);
if (left.second == right.second) {
return {root, left.second + 1};
}
else if (left.second < right.second) {
return {right.first, right.second + 1};
}
else {
return {left.first, left.second + 1};
}
}
public:
TreeNode* lcaDeepestLeaves(TreeNode* root) {
return dfs(root).first;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
Author: LetMeFly
Date: 2025-04-05 00:49:25
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-05 00:58:30
'''
from typing import Tuple, Optional


# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def dfs(self, root: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]:
if not root:
return (root, 0)
left = self.dfs(root.left)
right = self.dfs(root.right)
if left[1] > right[1]:
return (left[0], left[1] + 1)
elif left[1] < right[1]:
return (right[0], right[1] + 1)
return (root, left[1] + 1)

def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
return self.dfs(root)[0]

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
* @Author: LetMeFly
* @Date: 2025-04-05 00:59:21
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-04-05 01:03:59
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Pair<TreeNode, Integer> dfs(TreeNode root) {
if (root == null) {
return new Pair<>(root, 0);
}
Pair<TreeNode, Integer> left = dfs(root.left);
Pair<TreeNode, Integer> right = dfs(root.right);
if (left.getValue() > right.getValue()) {
return new Pair<>(left.getKey(), left.getValue() + 1);
} else if (left.getValue() < right.getValue()) {
return new Pair<>(right.getKey(), right.getValue() + 1);
}
return new Pair<>(root, left.getValue() + 1);
}

public TreeNode lcaDeepestLeaves(TreeNode root) {
return dfs(root).getKey();
}
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
* @Author: LetMeFly
* @Date: 2025-04-05 01:05:07
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-04-05 01:11:09
*/
package main

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type pair struct{
node *TreeNode
depth int
}

func dfs(root* TreeNode) pair {
if root == nil {
return pair{root, 0}
}
left := dfs(root.Left)
right := dfs(root.Right)
if left.depth > right.depth {
return pair{left.node, left.depth + 1}
} else if left.depth < right.depth {
return pair{right.node, right.depth + 1}
}
return pair{root, left.depth + 1}
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
return dfs(root).node
}

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132725441


1123.最深叶节点的最近公共祖先
https://blog.letmefly.xyz/2023/09/06/LeetCode 1123.最深叶节点的最近公共祖先/
作者
发布于
2023年9月6日
许可协议