草庐IT

leetcode算法—236 二叉树的最近公共祖先（中等）

小胖学编程 2023-09-16 原文

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

一棵调皮的二叉树

1. 总结

  • 二叉树算法的核心就是遍历（前中后 序遍历算法）
  1. p、q两个节点如何在二叉树上定位到（前序遍历）；
  2. 若找到最近公共祖先，那么必须处理完左右节点后才能得到父节点（后序遍历）

源代码：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {


    /**
     * 二叉树的公共最近祖先
     * <p>
     * 22:42    info
     * 解答成功:
     * 执行耗时:7 ms,击败了99.22% 的Java用户
     * 内存消耗:40.2 MB,击败了90.74% 的Java用户
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归出口与递归逻辑
        if (root == null || root.val == q.val || root.val == p.val) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        //递归逻辑
        if (leftNode != null && rightNode != null) {
            return root;
        }
        if (leftNode != null && rightNode == null) {
            return leftNode;
        }
        if (leftNode == null && rightNode != null) {
            return rightNode;
        }
        return null;
    }
}

时间复杂度 O(N) ： 其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
空间复杂度 O(N)： 最差情况下，递归深度达到 N ，系统使用 O(N) 大小的额外空间。

leetcodemdashTreeNodesectionnull

有关leetcode算法—236 二叉树的最近公共祖先（中等）的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2

    假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案 您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

  4. ruby - 实现k最近邻需要哪些数据？ - 2

    我目前有一个reddit克隆类型的网站。我正在尝试根据我的用户之前喜欢的帖子推荐帖子。看起来K最近邻或k均值是执行此操作的最佳方法。我似乎无法理解如何实际实现它。我看过一些数学公式(例如k表示维基百科页面)，但它们对我来说并没有真正意义。有人可以推荐一些伪代码，或者可以查看的地方，以便我更好地了解如何执行此操作吗？ 最佳答案 K最近邻(又名KNN)是一种分类算法。基本上，您采用包含N个项目的训练组并对它们进行分类。如何对它们进行分类完全取决于您的数据，以及您认为该数据的重要分类特征是什么。在您的示例中，这可能是帖子类别、谁发布了该项

  5. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  6. ruby - 在 Ruby 模块中定义公共(public)方法？ - 2

    我一定是犯了n00b错误。我编写了以下Ruby代码:moduleFoodefbar(number)returnnumber.to_s()endendputsFoo.bar(1)测试.rb:6:in':undefinedmethodbar'forFoo:Module(NoMethodError)我想在名为Foo.bar的模块上定义一个方法。但是，当我尝试运行代码时，出现未定义方法错误。我做错了什么？ 最佳答案 你可以这样做:moduleFoodefself.bar(number)number.to_sendendputsFoo.bar

  7. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  8. ruby-on-rails - 获取最近发生的星期三？ - 2

    如何使用Ruby(和Rails，如果有相关的辅助方法)获取最近发生的星期三？最终需要实际日期(5/1/2013)。 最佳答案 time=Time.nowdays_to_go_back=(time.wday+4)%7last_wed=days_to_go_back.days.ago 关于ruby-on-rails-获取最近发生的星期三？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions

  9. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  10. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

随机推荐