LeetCode算法题-Lowest Common Ancestor of a Binary Search Tree

LeetCode算法题-Lowest Common Ancestor of a Binary Search Tree

这是悦乐书的第197次更新,第203篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第59题(顺位题号是235)。给定二叉搜索树(BST),找到BST中两个给定节点的最低共同祖先(LCA)。根据维基百科上LCA的定义:“最低共同祖先在两个节点p和q之间定义为T中的最低节点,其中p和q都是后代(我们允许节点成为其自身的后代)。”

给定二叉搜索树:root = [6,2,8,0,4,7,9,null,null,3,5]

            6
          /   \
         2     8
        / \   / \
        0  4  7  9
          / \
         3   5

例如:

输入:root = [6,2,8,0,4,7,9,null,null,3,5],p = 2,q = 8

输出:6

说明:节点2和8的LCA为6。

输入:root = [6,2,8,0,4,7,9,null,null,3,5],p = 2,q = 4

输出:2

说明:节点2和4的LCA是2,因为节点可以是其自身的后代,根据LCA的定义。

注意:

  • 所有节点的值都是唯一的。

  • p和q不同,两个值都将存在于BST中。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

利用迭代的方法。二叉搜索树的特点是 左节点的值 < 根节点的值 < 右节点的值,如果p和q的节点值都小于当前节点,此时指针应该移动到当前节点的左节点,再去比较。如果p和q的节点值都大于当前节点,此时指针应该移动到当前节点的右节点,再去比较。否则就返回当前节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            return root;
        }
    }
    return root;
}

03 第二种解法

利用递归的方法,判断逻辑和迭代的解法一样。如果当前节点的值比p和q中最大值都要大,因为当前节点的左子节点值肯定小于当前节点的值,所以要往当前节点的左子节点方向移动。如果当前节点的值比p和q中最小值都要小,因为当前节点的右子节点值肯定大于当前节点的值,所以要往当前节点的右子节点方向移动。然后再去判断。

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    if (root.val > Math.max(p.val, q.val)) {
        return lowestCommonAncestor2(root.left, p, q);
    }
    if (root.val < Math.min(p.val, q.val)) {
        return lowestCommonAncestor2(root.right, p, q);
    }
    return root;
}

04 小结

算法专题目前已连续日更超过一个月,算法题文章59+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

转载于:https://www.cnblogs.com/xiaochuan94/p/10094634.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101273.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 红队评估实战靶场(1)

    0x00前言[滑稽][滑稽]又是我,我又来发水文了,这几天打靶机打上瘾了,再来更新篇靶机的文章0x01靶机渗透配置好靶机后,这里需要打开win7,来到c盘目录下启动phpstudy启动完成后

    2021年12月11日
  • idea git 合并分支到指定分支_idea合并分支到另一个分支

    idea git 合并分支到指定分支_idea合并分支到另一个分支ideagit的使用(四)git建立分支与合并分支作者:马育民 • 2017-11-1017:05 • 阅读:103571.为什么要建立分支git默认的主分支名字为master,一般团队开发时,都不会在master主分支上修改代码,而是建立新分支,测试完毕后,在将分支的代码合并到master主分支上。2.操作如下:2.1ideagit分支的操作ideagit的操作在右下角,如下图:说明…

  • java四舍五入(保留两位小数)[通俗易懂]

    java四舍五入(保留两位小数)[通俗易懂]1.最简单的方法:floata=123.4567f;这里的100就是2位小数点,如果要其它位,如4位,这里两个100改成10000floatb=(float)(Math.round(a*100))/100;doublef=111231.5585;BigDecimalb=newBigDecimal(f);doublef1=b.setScale(2,BigDecimal.ROUND_HALF_UP

  • 使用python创建数组的方法[通俗易懂]

    使用python创建数组的方法[通俗易懂]本文介绍两种在python里创建数组的方法。第一种是通过字典直接创建,第二种是通过转换列表得到数组。方法1.字典创建(1)导入功能(2)创立字典(3)将字典带上索引转换为数组代码示例如下:importnumpyasnpimportpandasaspddata={“name”:[‘xiaozhang’,‘xiaoli’,‘lily’,‘tony’],“sex”:[‘bo…

  • 马哥学习—-李洋个人笔记–启动故障排除

    马哥学习—-李洋个人笔记–启动故障排除故障1删除/boot之后的恢复步骤:1重启电源,迅速按esc进去选择启动模式,然后选cd-rom这项(从光驱启动)2重启后进入救援模式(选择rescue),选择语言和键盘布局后,一路回车到下一步。3询问是否需要网络选项,一般来说,救援模式不需要网络,选择no,回车进入下一步。4这一步提示内容大意为:救援系统将尝试寻找你的linux安装,并在目录mnt/sysimage下安装它…

  • 浅析Promise用法[通俗易懂]

    浅析Promise用法[通俗易懂]浅析Promise用法要理解Promise要知道没有Promise的回调地狱如何插入一段漂亮的代码片Promise语法与then的用法所谓Promise,简单说就是一个容器,里面保存着某个未来才会结束的事件(通常是一个异步操作)的结果。从语法上说,Promise是一个对象,从它可以获取异步操作的消息。Promise提供统一的API,各种异步操作都可以用同样的方法进行处理。Promis…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号