DeepSeek LeetCode 236. 二叉树的最近公共祖先 Java实现-北京尧图网络

LeetCode 236. 二叉树的最近公共祖先 Java 实现思路递归后序遍历从根节点开始递归· 如果当前节点为空或当前节点就是 p 或 q直接返回当前节点。· 分别递归左右子树得到 left 和 right。· 如果 left 和 right 都非空说明 p 和 q 分别在左右两侧当前节点就是最近公共祖先。· 否则返回非空的那一个说明两个目标节点都在同一侧或只找到了其中一个。Java 代码classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){// 递归终止条件if(rootnull||rootp||rootq){returnroot;}// 后序遍历先处理左右子树TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);// 左右都找到了说明 p、q 分布在两侧当前节点就是 LCAif(left!nullright!null){returnroot;}// 否则返回非空的那一侧returnleft!null?left:right;}}复杂度分析· 时间复杂度O(n)每个节点最多访问一次。· 空间复杂度O(h)递归栈深度为树高。最坏情况下链状树为 O(n)。示例// 树结构// 3// / \// 5 1// / \ / \// 6 2 0 8// / \// 7 4p5,q1→3p5,q4→5p6,q4→5关键点· 递归函数含义在以 root 为根的子树中寻找 p 和 q 的最近公共祖先。· 如果当前节点就是 p 或 q直接返回它因为不可能再往下找到更近的祖先。· 左右子树返回值都非空说明两个目标节点分居两侧当前节点即为答案。· 只需要一次 DFS无需额外存储路径。附迭代写法父指针祖先集合classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){MapTreeNode,TreeNodeparentnewHashMap();DequeTreeNodestacknewArrayDeque();parent.put(root,null);stack.push(root);// 遍历整棵树记录每个节点的父节点while(!parent.containsKey(p)||!parent.containsKey(q)){TreeNodenodestack.pop();if(node.left!null){parent.put(node.left,node);stack.push(node.left);}if(node.right!null){parent.put(node.right,node);stack.push(node.right);}}// 记录 p 到根的所有祖先SetTreeNodeancestorsnewHashSet();while(p!null){ancestors.add(p);pparent.get(p);}// 从 q 向上找第一个在 p 祖先集合中的节点while(!ancestors.contains(q)){qparent.get(q);}returnq;}}迭代写法时间复杂度 O(n)空间复杂度 O(n)适合不想用递归或树很深的情况。

DeepSeek LeetCode 236. 二叉树的最近公共祖先 Java实现

相关推荐

26年程序员转AI指南：收藏这份学习路线，轻松拥抱大模型时代！

PHP登录安全实战：TOTP多因素认证、风控拦截与Redis会话一致性

数组：算法竞赛的地基，从内存模型到高级数据结构的底层逻辑

更多资讯

回溯法详解：LeetCode 46. 全排列

【Web全栈进阶】PostgreSQL上手：Docker跑库 + 把早报站从SQLite迁过去

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

手表页面退出后传感器还在采样：HarmonyOS 穿戴订阅的功耗预算与生命周期

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？