LeetCode实战：二叉搜索树的最近公共祖先
背景
- 为什么你要加入一个技术团队？
- 如何加入 LSGO 软件技术团队？
- 我是如何组织“算法刻意练习活动”的？
- 为什么要求团队的学生们写技术Blog
题目英文
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes’ values will be unique.
- p and q are different and both values will exist in the BST.
题目中文
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
算法实现
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val = x; }* }*/public class Solution
{public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if (root.val == p.val || root.val == q.val)return root;if (root.val > p.val && root.val < q.val)return root;if (root.val < p.val && root.val > q.val)return root;if (root.val < p.val && root.val < q.val){return LowestCommonAncestor(root.right, p, q);}return LowestCommonAncestor(root.left, p, q);}
}
实验结果
- 状态：通过
- 27 / 27 个通过测试用例
- 执行用时: 128 ms, 在所有 C# 提交中击败了 95.71% 的用户
- 内存消耗: 30.8 MB, 在所有 C# 提交中击败了 7.69% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
- LeetCode实战：螺旋矩阵
- LeetCode实战：螺旋矩阵 II
- LeetCode实战：买卖股票的最佳时机
- LeetCode实战：买卖股票的最佳时机 II
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “位运算”类算法
- LeetCode实战：格雷编码
7. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
- LeetCode实战：字符串相加
- LeetCode实战：字符串相乘
8. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
9. “哈希”类算法
- LeetCode实战：两数之和
10. “排序”类算法
- LeetCode实战：合并两个有序数组
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
11. “搜索”类算法
- LeetCode实战：搜索二维矩阵
- LeetCode实战：子集
12. “动态规划”类算法
- LeetCode实战：最长回文子串
- LeetCode实战：最大子序和
- LeetCode实战：不同路径
13. “回溯”类算法
- LeetCode实战：全排列
14. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
[转载] 杜拉拉升职记——02 单相思与性骚扰
来源：李可. 杜拉拉升职记(第三版). 西安: 陕西师范大学出版社, 2010, 5. 02 单相思与性骚扰的区别 拉拉注意到，DB所有经理办公室沿走道的这一面，都是用大块的玻璃来做间隔墙。 拉拉问海伦：“这么设计是为了美观吗？” …
走进云计算与虚拟化的底层核心
本文讲的是走进云计算与虚拟化的底层核心,2012年3月在国务院政府工作报告附录部分中，政府对云计算给出了官方的解释，体现了政府对云计算产业的高度重视和美好愿景。云计算在工作报告中是这样定义的：“云计算是基于互联网的服务的增加、使用和…
LeetCode实战：LRU缓存机制
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Design and implement a data structure for Least Recently Used (LRU) cache. It should …
探索性测试，笔记二
测试十戒律： 1、你应该使用大量输入，来反复锤炼被测的应用程序 *大规模的随机测试（自动化），而且有助于理解输入和输出的关系 2、你应当贪图你的邻居的应用程序 3、你应当亲自寻找睿智的预言家 *对应的输入是否有对应的…
python 监控windows磁盘空间和备份大小
#!/usr/bin/env python # Version 3.5.2 # __auth__ 无名小妖 import os import time import sendmail import psutil import collectionsdisk_used collections.OrderedDict() cur_time time.time() # current_day cur_time - cur_time % 86400 root_dir ["D:\\bac…
如何高效学习java课程
想要快速进入到java行业，进行系统的培训和有效的学习是非常重要的，那么短时间内如何高效学习java课程呢?来看看下面小编的详细介绍吧。 如何高效学习java课程? 1. 克服自身惰性，学习环境更佳。 参加Java培训机构学习的话，…
2021年web前端发展方向有哪些
一年转瞬即逝，仅仅一年的时间，就能发生很多事情，近几年web前端行业越来越受到大家的关注，很多人都想看看2021年web前端发展方向有哪些?下面来看看小编详细的介绍。 2021年web前端发展方向有哪些? 1、TypeScript爆发增长 从2019年…
weblogic服务器部署的程序，如何直接通过IP访问（即URL中去掉工程名）
用weblogic部署的程序，怎么能够直接通过IP访问呢？ 下面就是了 打开你的工程，看看webroot下的WEB-INF中有没有一个weblogic.xml文件。 1、如果没有，自己建一个，里面写上： <?xml version"1.0" …
LeetCode实战：二叉搜索树中第K小的元素
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary search tree, write a function kthSmallest to find the kth smallest ele…
xml文件-1
2019独角兽企业重金招聘Python工程师标准>>> 1 Xml简单的历史介绍 1969 gml(通用标记语言) [主要的目的是要在不同的机器进行通信的数据规范] 1985 sgml(标准通用标记语言) 1993 html (www网) Html语言本身是有一些缺陷的 (1)标记不能自定义 <html> <table…
学习web前端难不难
学习web前端难不难?这是很多同学都会问到的问题，web前端在目前互联网行业的发展前景是非常可观的，想要进入到这个行业的人有很多，下面我们来看看具体的介绍。 学习web前端难不难?首先你要明白你需要什么 前发展还是后发展?定好系统的学习目…
Android对话框-下篇-之设置activity为Dialog
有人希望做出来的应用程序是一个漂浮在手机主界面的东西，那么很 简单你只需要设置一下Activity的主题就可以了在AndroidManifest.xml 中定义Activity的 地方一句话：android:theme"android:style/Theme.Dialog" 这就使你的应用程序变成对话框的…
Codeforces 846 B Math Show DFS + 贪心
题目链接： http://codeforces.com/contest/846/problem/B 题目描述： 有N个节点， 每个节点有相同的K个子节点， 每个子节点有时间花费，完成一个子节点获得1分， 每完成一个节点的所有子节点获得额外一分&…
LeetCode实战：二叉树的最近公共祖先
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the …
学习UI设计都需要了解哪些知识
由于UI设计的高薪，很多人都萌生了想要学习UI设计的想法，但是小编提醒大家，学习UI设计之前一定要做足功课，了解UI设计基本知识，再看看自己是否适合学习，下面小编就为大家详细的介绍一下学习UI设计都需要了解…
Marty Cagan：怎样寻找出色的产品经理
《程序员杂志》的文章，原帖位于http://www.programmer.com.cn/7760/ 写的很好，自己转贴存储一下，也符合Product Owner的要求，就是……要求太高了！本文是他回顾自己二十多年来从事软件产品管理工作的总结和经验分享&…
LeetCode实战：除自身以外数组的乘积
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given an array nums of n integers where n > 1, return an array output such that ou…
PHP+MySql获取自动增长字段的新添加记录ID值
PHPMySql获取新添加记录的ID值 1.假设字段名称为recordID 2.字段属性须设为：auto_increment 3.添加数据后使用 $newID mysql_insert_id(); 得到ID值 ASP获取即时ID值 ASPAccess2000 1.要获取的ID值字段属性必须设为：自动编号(我们假设字段名为recordID)…
MyBatis框架添加客户有哪些步骤
在MyBatis的映射文件中，添加操作是通过元素来实现的。例如，向数据库中的t_customer表中插入一条数据可以通过如下配置来实现。 在上述配置代码中，传入的参数是一个Customer类型，该类型的参数对象被传递到语句中时，#{us…
磁盘IO的总结
转自：http://simpleframework.net/blog/v/8486.html 1. 完全随机写还是跳跃，5倍的性能差距！ 全随机写无疑是最慢的写入方式，在logic dump测试中很惊讶的发现，将200M的内存数据随 机的写入到100G的磁盘数据里面…
UI设计培训之设计中的点线面-面
想要学好UI设计，从事UI设计工作，那么理论基础知识一定要会，今天小编为大家整理的就是关于UI设计中的点线面-面，在平面构成三要素中面是相对占空间最大的元素，在设计中也包含和表现更加强烈的情感色彩，有明显…
projecteuler_problem10
problem10 地址：https://projecteuler.net/problem10。 源码：gitcode.aliyun.com:qianlizhixing12/ProjectEuler.git。问题：找到2000000内质数和。 #include <stdio.h> #include <math.h> #include "debug.h" #include…
LeetCode实战：排序链表
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Sort a linked list in O(n log n) time using constant space complexity. Example 1: I…
技术图文：双指针在链表问题中的应用
背景 最近这段时间团队在进行算法刻意练习活动，我带着同学们刷 leetcode 的“腾讯精选练习（50）题”，参见：我是如何组织“算法刻意练习活动”的？ 在做题的过程中，同学们讨论比较多的是链表中遇…
[BuildRelease]build number / id
build number， 也称为build id， 在build release的流程中唯一标示一个build，也是正式的产品的product version 和file version后两位（Major.minor.xxx.xxx）的来源，可以使用合适的方法将build number转化到p…
Windows Azure Storage (25) Azure Append Blob
《Windows Azure Platform 系列文章目录》 在笔者之前的文章中，我们介绍了Azure Blob 有两种：Block Blob和Page Blob。 在这里笔者介绍Blob的第三种：Append Blob。 概念： 1.Append Blob概念类似于Block Blob，因为都是由…
学python培训到底能干嘛
Python是在人工智能领域发挥着很重要的作用的，现在依旧有很多人对Python这项技术不是很了解，学Python培训到底能干嘛?下面小编来为大家做下详细的介绍。 python其实并不难学，对于初学者和完成普通任务，Python语言是非常简单易用的…
使用VB.NET加快代码开发速度
以前在学校时，编写代码都是使用C#，习惯了C#的代码习惯，等工作后由于工作需要逐渐的开始采用了VB.NET开发项目，渐渐地喜欢上了VB.NET，现在我就罗列一些VB.NET加速代码开发的方法。 一、智能感知 做.NET开发的许多人都知…
技术图文：举例详解Python中 split() 函数的使用方法
背景 这篇文章主要介绍Python中的split()函数的使用方法，split()函数通常用于将字符串切片并转换为列表，需要的朋友可以参考一下。 技术分析 Python中有split()和os.path.split()两个函数，具体作用如下： split()：拆…
Burning
转载于:https://www.cnblogs.com/kuiyuan/archive/2011/09/02/2163621.html