最深叶节点的最近公共祖先 图解题解
这道题到底在问什么
- 输入
- root=[50,30,80,60,20,10,90,null,null,70,40]
- 输出
- 节点 20(最深叶 70、40 的 LCA)
最优解：一步一步想明白
- 3记住「左右等深 → 当前点当 LCA;一边更深 → 跟更深那边的 LCA」,下面每帧都在套它。
- 4从根 50 出发做后序遍历:先把左右子树都递归算完,再合并出当前节点要返回的 (深度, LCA)。
- 5走到节点 50。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
- 6走到节点 30。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
- 7走到叶子 60。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
- 8叶子 60 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 60)。标绿表示结算好了。
- 9走到节点 20。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
- 10走到叶子 70。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
- 11叶子 70 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 70)。标绿表示结算好了。
- 12走到叶子 40。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
- 13叶子 40 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 40)。标绿表示结算好了。
- 14回到 20 结算:左右一样深(都是 1),所以在 20 这棵子树里、最深叶的 LCA 就是 20 自己;它会作为 (深度, LCA) 往上返回,全局答案还要等根节点合并时再定。于是 20 返回 (深度 2, LCA = 20)。
- 15回到 30 结算:右边更深(2 大于 1),最深叶只在右子树,跟着右边的 LCA 20。于是 30 返回 (深度 3, LCA = 20)。
- 16走到节点 80。先别急着下结论,得先把它的左、右子树各自的 (深度, LCA) 都算出来。
- 17走到叶子 10。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
- 18叶子 10 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 10)。标绿表示结算好了。
- 19走到叶子 90。叶子没有孩子,它自己就是这棵小子树里唯一、也是最深的叶子。
- 20叶子 90 结算:它这棵子树高度是 1,最深叶就是它自己,返回 (深度 1, LCA = 90)。标绿表示结算好了。
- 21回到 80 结算:左右一样深(都是 1),所以在 80 这棵子树里、最深叶的 LCA 就是 80 自己;它会作为 (深度, LCA) 往上返回,全局答案还要等根节点合并时再定。于是 80 返回 (深度 2, LCA = 80)。
- 22回到 50 结算:左边更深(3 大于 2),最深叶只在左子树,跟着左边的 LCA 20。于是 50 返回 (深度 4, LCA = 20)。
- 23根结算完,它返回的 LCA 就是答案:节点 20(红色标出)。它正是最深那两个叶子 70、40 的最近公共祖先。
⚠️ 容易写错的地方
✗ 错：自顶向下先扫最深叶再求 LCA
✓ 对：后序自底向上,一次返回 (深度, LCA)
后序天然保证先有左右子树结果才合并当前,一遍就够;自顶向下要先扫一遍求最深、再扫一遍求 LCA,更绕
✗ 错：深度相等时只返回一边的孩子
✓ 对：dl 等于 dr 时返回当前节点
dl 等于 dr 且大于 0 时左右两侧都有同高最深叶,能同时罩住它们的最近节点就是当前节点;dl 等于 dr 等于 0 时当前节点本身是叶子、是唯一最深叶;两种情况都返回当前节点,不是某一边
✗ 错：只比较深度忘了把 LCA 一起带上
✓ 对：返回值是 (深度, LCA) 二元组,两样都要传
光有深度无法定位 LCA;深度用来比哪边深、LCA 用来逐层上传答案
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
class 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]C++
#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* lcaDeepestLeaves(TreeNode* root){ function<pair<int,TreeNode*>(TreeNode*)> dfs=[&](TreeNode*n){ if(!n)return pair<int,TreeNode*>{0,nullptr}; auto L=dfs(n->left),R=dfs(n->right); if(L.first==R.first)return pair<int,TreeNode*>{L.first+1,n}; return L.first>R.first?pair<int,TreeNode*>{L.first+1,L.second}:pair<int,TreeNode*>{R.first+1,R.second};}; return dfs(root).second; }};Java
import java.util.*;
class TreeNode{int val;TreeNode left,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{ public TreeNode lcaDeepestLeaves(TreeNode root){ return dfs(root).node; } static class Res{int d;TreeNode node;Res(int d,TreeNode n){this.d=d;node=n;}} Res dfs(TreeNode n){ if(n==null)return new Res(0,null); Res l=dfs(n.left),r=dfs(n.right); if(l.d==r.d)return new Res(l.d+1,n); return l.d>r.d?new Res(l.d+1,l.node):new Res(r.d+1,r.node); } }复杂度
时间
O(n)
后序 DFS 每个节点恰好访问一次,合并左右结果是常数,n 是节点数
空间
O(h)
递归栈深度等于树高 h,最坏树退化成链时是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最深叶节点的最近公共祖先 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用两遍遍历做?+
可以。第一遍求出最大深度并收集所有最深叶子,第二遍对这组叶子求 LCA。但要遍历两遍、还得存最深叶集合;本题的后序一次返回 (深度, LCA) 更省,一遍 O(n)、额外空间只用递归栈。
返回的 LCA 一定是某个最深叶的祖先吗?+
是。等深且深度大于 0 时,当前节点同时覆盖左右两边的最深叶;等深且深度为 0 时,当前节点就是叶子本身;不等深时跟着更深那边的 LCA,而那个 LCA 本身就是那一侧最深叶的祖先。逐层上传后,根返回的 LCA 就是全部最深叶的最近公共祖先。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最深叶节点的最近公共祖先 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。