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

【力扣打卡系列】二叉树的最近公共祖先

坚持按题型打卡&刷&梳理力扣算法题系列,语言为go,Day18

二叉树的最近公共祖先
  • 题目描述
    在这里插入图片描述
  • 解题思路
    • 最近公共祖先
    • 分类讨论
      • 当前节点是空节点(返回当前节点)
      • 当前节点是p(返回当前节点)
      • 当前节点是q(返回当前节点)
      • 其他:是否找到p或q
        • 左右子树都找到(返回当前节点)
        • 只有左子树找到(返回递归左子树的结果)
        • 只有右子树找到(返回递归右子树的结果)
        • 左右子树都没有找到(返回空节点)
  • 代码参考
/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil || root == p || root == q{return root}left := lowestCommonAncestor(root.Left,p,q)right := lowestCommonAncestor(root.Right,p,q)if left != nil && right != nil{return root}if left != nil{return left}else{return right}
}
  • tips
    • 注意go中的false条件不能省略写,一定要写成==nil的形式来判断
二叉搜索树的最近公共祖先
  • 题目描述
    在这里插入图片描述
  • 解题思路
    • 可以剪枝
    • 题目保证p和q都在树中,根节点肯定不是空节点,所以不需要判断当前节点是空节点的情况
    • 分类讨论yyds!(见下图)
      在这里插入图片描述
  • 代码参考
/*** Definition for a binary tree node.* type TreeNode struct {*     Val   int*     Left  *TreeNode*     Right *TreeNode* }*/func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if q.Val<root.Val && p.Val<root.Val{return lowestCommonAncestor(root.Left,p,q)}else if q.Val>root.Val && p.Val>root.Val{return lowestCommonAncestor(root.Right,p,q)}else{return root}if root == p || root == q{return root} return root
}

http://www.mrgr.cn/news/62854.html

相关文章:

  • Rust:文档注释 //! 和 ///
  • 如何用Python同时抓取多个网页:深入ThreadPoolExecutor
  • 使用 Kibana 将地理空间数据导入 Elasticsearch 以供 ES|QL 使用
  • 深入探索:深度学习在时间序列预测中的强大应用与实现
  • 基础知识-因果分析-daytwo-2 概率及其计算
  • HTMLCSS:3D旋转动画机器人摄像头
  • 2024最新Linkedln领英养号方法总结
  • 【数学二】线性代数-行列式
  • 早点包子店点餐的软件下载和点餐操作教程 佳易王餐饮点餐管理系统操作方法
  • redis安装使用
  • 攻防世界 MISC miao~详解
  • Android——Activity生命周期
  • 面试题整理 2
  • net framework 3.5组件更新失败错误代码0x80072f8f怎样解决
  • LC:贪心题解
  • Javaweb梳理5——约束
  • 10 go语言(golang) - 数据类型:哈希表(map)及原理(二)
  • LoRA微调大模型 - 从主元 pivot 的角度看矩阵的秩
  • 前端如何解决浏览器input输入框密码自动填充的问题
  • 【C/C++】字符/字符串函数(1)——由string.h提供
  • DBeaver如何插入一行新数据或者复制一行新数据,真方便
  • selenium无头浏览器截图并以邮件发送
  • 【设计模式】如何用C++实现依赖倒置
  • AcWing 1069 凸多边形的划分 区间dp + 高精度
  • 普通人的核心竞争力
  • Vim的配置