题目描述
思路解析动画文字版
记住「左右等深 → 当前点当 LCA;一边更深 → 跟更深那边的 LCA」,下面每帧都在套它。
准备 · 从根出发：从根 50 出发做后序遍历:先把左右子树都递归算完,再合并出当前节点要返回的 (深度, LCA)。
访问 50：走到节点 50。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
访问 30：走到节点 30。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
访问 60：走到叶子 60。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
结算 60：叶子 60 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 60)。标绿表示结算好了。
访问 20：走到节点 20。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
访问 70：走到叶子 70。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
结算 70：叶子 70 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 70)。标绿表示结算好了。
访问 40：走到叶子 40。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
结算 40：叶子 40 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 40)。标绿表示结算好了。
结算 20：回到 20 结算:左右一样深(都是 1),所以在 20 这棵子树里、最深叶的 LCA 就是 20 自己;它会作为 (深度, LCA) 往上返回,全局答案还要等根节点合并时再定。于是 20 返回 (深度 2, LCA = 20)。
结算 30：回到 30 结算:右边更深(2 大于 1),最深叶只在右子树,跟着右边的 LCA 20。于是 30 返回 (深度 3, LCA = 20)。
访问 80：走到节点 80。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
访问 10：走到叶子 10。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
结算 10：叶子 10 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 10)。标绿表示结算好了。
访问 90：走到叶子 90。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
结算 90：叶子 90 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 90)。标绿表示结算好了。
结算 80：回到 80 结算:左右一样深(都是 1),所以在 80 这棵子树里、最深叶的 LCA 就是 80 自己;它会作为 (深度, LCA) 往上返回,全局答案还要等根节点合并时再定。于是 80 返回 (深度 2, LCA = 80)。
结算 50：回到 50 结算:左边更深(3 大于 2),最深叶只在左子树,跟着左边的 LCA 20。于是 50 返回 (深度 4, LCA = 20)。
答案：根结算完,它返回的 LCA 就是答案:节点 20(红色标出)。它正是最深那两个叶子 70、40 的最近公共祖先。
边界:单节点=自己;完美树=根;链=最深那个叶子。
两个高频追问:可两遍但后序一遍更优;返回的 LCA 必是最深叶的祖先。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val=val; self.left=left; self.right=rightclass Solution: def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(n): if not n: return (0,None) dl,ln=dfs(n.left); dr,rn=dfs(n.right) if dl==dr: return (dl+1,n) return (dl+1,ln) if dl>dr else (dr+1,rn) return dfs(root)[1]复杂度
- 时间：O(n)，后序 DFS 每个节点恰好访问一次,合并左右结果是常数,n 是节点数
- 空间：O(h)，递归栈深度等于树高 h,最坏树退化成链时是 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能用两遍遍历做?
追问返回的 LCA 一定是某个最深叶的祖先吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大层内元素和
LeetCode 1161 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题