小程序是什么,沧州seo排名,湖南长沙公司有哪些,简单的管理系统【LetMeFly】1123.最深叶节点的最近公共祖先
力扣题目链接#xff1a;https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/
给你一个有根节点 root 的二叉树#xff0c;返回它 最深的叶节点的最近公共祖先 。
回想一下#xff1a;
叶节点 是二叉树…【LetMeFly】1123.最深叶节点的最近公共祖先
力扣题目链接https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/
给你一个有根节点 root 的二叉树返回它 最深的叶节点的最近公共祖先 。
回想一下
叶节点 是二叉树中没有子节点的节点树的根节点的 深度 为 0如果某一节点的深度为 d那它的子节点的深度就是 d1如果我们假定 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)
们把最深的叶节点的最近公共祖先称之为 lca \textit{lca} lca节点。
编写一个函数dfs(root)返回以root为根的子树的{lca, 深度}。 如果左子树更深则返回{左子的lac, 左子深度 1} 如果右子树更深则返回{右子的lac, 右子深度 1} 否则左右子树深度相同则返回{root左子深度 1} 时间复杂度 O ( n ) O(n) O(n)其中 n n n为二叉树节点个数 空间复杂度 O ( n ) O(n) O(n)
AC代码
C
typedef pairTreeNode*, 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
# from typing import Optional# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def dfs(self, root: Optional[TreeNode]):if not root:return [None, 0]left self.dfs(root.left)right self.dfs(root.right)if left[1] right[1]:return [root, left[1] 1]elif left[1] right[1]:return [right[0], right[1] 1]else:return [left[0], left[1] 1]def lcaDeepestLeaves(self, root: Optional[TreeNode]) - Optional[TreeNode]:return self.dfs(root)[0] 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132725441
