当前位置: 首页 > news >正文

二叉树最近公共祖先

LCR 194. 二叉树的最近公共祖先

LCR 193. 二叉搜索树的最近公共祖先 也是一样的做法

二叉树的公共祖先的定义:对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先

分类讨论:

  1. 当前节点为空 or 当前节点等于p or 当前节点等于q,返回当前节点
  2. 左右子树相等,返回当前节点
  3. 左子树为空,右子树不为空,返回右子树,反之左子树,都为空,就返回空即可
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) {return root;}TreeNode lnode = lowestCommonAncestor(root.left, p, q);TreeNode rnode = lowestCommonAncestor(root.right, p, q);if(lnode != null && rnode != null) {return root;}return lnode != null ? lnode : rnode;
}
http://www.hskmm.com/?act=detail&tid=13860

相关文章:

  • AI 编程“效率幻觉”:为何你感觉快了,项目却慢了?
  • lc1033-移动石子直到连续
  • 一些正在制作的“格林达姆”测试项目,以及“假无损”
  • 个人项目
  • 北京 意大利学签 北京意大利签证中心 贵宾 vip vfs
  • 第1周
  • 多商家在线客服系统 - 客服用户表设计方案
  • 九月22号
  • 25.9.22 继续MySQL
  • 使用python读取windows注册表
  • 当日总结
  • 3123004481
  • 使用python读取windows日志表
  • 开机RAM分析调试SOP
  • 9.20 模拟赛 T4
  • 2025.9.21 测试 (a1a2a3a4a5)
  • 原码、反码和补码
  • Русский язык
  • 基于Hex Editor Neo的二进制文件模板
  • 【F#学习】字符
  • kubebuilder创建Operator示例
  • 集训总结(八)
  • 使用try-finally结构执行状态重置
  • java03预习
  • x6831卡顿分析
  • 实测对比:权威榜单之微信排版软件Top5(含详细测评)
  • 【F#学习】布尔运算优先级
  • 粘连字符验证码的分割与识别思路
  • 深入解析:【Spark+Hive+hadoop】基于spark+hadoop基于大数据的人口普查收入数据分析与可视化系统
  • part 8