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

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

坚持按题型打卡&刷&梳理力扣算法题系列,语言为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.kler.cn/a/373707.html

相关文章:

  • [前端面试]计算机网络
  • Python实现深度学习模型预测控制(tensorflow)DL-MPC(Deep Learning Model Predictive Control
  • golang 高阶函数
  • Vuestic 数据表格 使用demo
  • 常见的机器学习模型汇总
  • 聆听用户声音的3个方法,挖掘客户真实潜在需求
  • Qt 窗口部件的焦点策略
  • Python 自动化运维:CI/CD与DevOps实践的深度探讨
  • Kubernetes:(三)Kubeadm搭建K8s 1.20集群
  • 探索面向对象的高级特性与设计模式(2/5)
  • 爱普生SG-8101CA可编程晶振的应用领域
  • Oracle视频基础1.3.2练习
  • 基于 ThinkPHP+Mysql 灵活用工_灵活用工系统_灵活用工平台
  • Kubernetes 1.23.1 集群安装Istio 1.17.8
  • Maven:详解 clean 和 install 命令的使用
  • Unreal5从入门到精通之如何解决在VR项目在头显中卡顿的问题
  • 图技术发展简史
  • 全桥PFC电路及MATLAB仿真
  • 强化学习DQN实践(gymnasium+pytorch)
  • 快速全面系统的学习Python基础语法知识
  • 【ChatGPT】通过明确的角色设定提高ChatGPT输出的专业性
  • 【Linux】Zookeeper 部署
  • LeetCode 202 - 快乐数
  • python multiprocessing lock锁在相同父进程ID起作用
  • 奥数与C++小学四年级(第十二题 装礼盒)
  • 【unity框架开发14】状态机的封装与实现