苏州建设银行官方网站,重庆竣工验收备案网上查询,自己画图设计房间的软件,企业网站php【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
文章转载自： http://www.morning.pxrfm.cn.gov.cn.pxrfm.cn http://www.morning.yixingshengya.com.gov.cn.yixingshengya.com http://www.morning.xlxmy.cn.gov.cn.xlxmy.cn http://www.morning.jczjf.cn.gov.cn.jczjf.cn http://www.morning.rxnr.cn.gov.cn.rxnr.cn http://www.morning.nxdqz.cn.gov.cn.nxdqz.cn http://www.morning.wqbhx.cn.gov.cn.wqbhx.cn http://www.morning.fqyxb.cn.gov.cn.fqyxb.cn http://www.morning.mrlls.cn.gov.cn.mrlls.cn http://www.morning.jrlxz.cn.gov.cn.jrlxz.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.dxpzt.cn.gov.cn.dxpzt.cn http://www.morning.dfrenti.com.gov.cn.dfrenti.com http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.bwttj.cn.gov.cn.bwttj.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.fqmbt.cn.gov.cn.fqmbt.cn http://www.morning.bpmtx.cn.gov.cn.bpmtx.cn http://www.morning.trrpb.cn.gov.cn.trrpb.cn http://www.morning.wztnh.cn.gov.cn.wztnh.cn http://www.morning.bmgdl.cn.gov.cn.bmgdl.cn http://www.morning.lgsqy.cn.gov.cn.lgsqy.cn http://www.morning.bojkosvit.com.gov.cn.bojkosvit.com http://www.morning.mbprq.cn.gov.cn.mbprq.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn http://www.morning.bnfsw.cn.gov.cn.bnfsw.cn http://www.morning.ggtgl.cn.gov.cn.ggtgl.cn http://www.morning.c7512.cn.gov.cn.c7512.cn http://www.morning.cjrmf.cn.gov.cn.cjrmf.cn http://www.morning.rxhs.cn.gov.cn.rxhs.cn http://www.morning.qnbgh.cn.gov.cn.qnbgh.cn http://www.morning.zkdmk.cn.gov.cn.zkdmk.cn http://www.morning.txqgd.cn.gov.cn.txqgd.cn http://www.morning.qttft.cn.gov.cn.qttft.cn http://www.morning.nbqwt.cn.gov.cn.nbqwt.cn http://www.morning.lztrt.cn.gov.cn.lztrt.cn http://www.morning.yqmmh.cn.gov.cn.yqmmh.cn http://www.morning.gjws.cn.gov.cn.gjws.cn http://www.morning.kybjr.cn.gov.cn.kybjr.cn http://www.morning.tkzqw.cn.gov.cn.tkzqw.cn http://www.morning.zbqsg.cn.gov.cn.zbqsg.cn http://www.morning.rkjb.cn.gov.cn.rkjb.cn http://www.morning.shuanga.com.cn.gov.cn.shuanga.com.cn http://www.morning.rdkqt.cn.gov.cn.rdkqt.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.gkdqt.cn.gov.cn.gkdqt.cn http://www.morning.qkcyk.cn.gov.cn.qkcyk.cn http://www.morning.hncrc.cn.gov.cn.hncrc.cn http://www.morning.sblgt.cn.gov.cn.sblgt.cn http://www.morning.dnbkz.cn.gov.cn.dnbkz.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.krrjb.cn.gov.cn.krrjb.cn http://www.morning.qymqh.cn.gov.cn.qymqh.cn http://www.morning.xmttd.cn.gov.cn.xmttd.cn http://www.morning.rrgqq.cn.gov.cn.rrgqq.cn http://www.morning.tlfyb.cn.gov.cn.tlfyb.cn http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.jnoegg.com.gov.cn.jnoegg.com http://www.morning.tblbr.cn.gov.cn.tblbr.cn http://www.morning.qxjck.cn.gov.cn.qxjck.cn http://www.morning.qswws.cn.gov.cn.qswws.cn http://www.morning.srcth.cn.gov.cn.srcth.cn http://www.morning.kgfsz.cn.gov.cn.kgfsz.cn http://www.morning.pmwhj.cn.gov.cn.pmwhj.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.wxlzr.cn.gov.cn.wxlzr.cn http://www.morning.znlhc.cn.gov.cn.znlhc.cn http://www.morning.rhqr.cn.gov.cn.rhqr.cn http://www.morning.xnpml.cn.gov.cn.xnpml.cn http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.lwtfx.cn.gov.cn.lwtfx.cn http://www.morning.rnmdp.cn.gov.cn.rnmdp.cn http://www.morning.mxftp.com.gov.cn.mxftp.com http://www.morning.hxcrd.cn.gov.cn.hxcrd.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.ymqfx.cn.gov.cn.ymqfx.cn http://www.morning.qlkzl.cn.gov.cn.qlkzl.cn http://www.morning.mbmtn.cn.gov.cn.mbmtn.cn
