当前位置：首页 > 编程日记 > 正文

LeetCode实战：二叉树的最近公共祖先

编程日记 2024-09-27 12:20:00

背景

为什么你要加入一个技术团队？
如何加入 LSGO 软件技术团队？
我是如何组织“算法刻意练习活动”的？
为什么要求团队的学生们写技术Blog

题目英文

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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 the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, 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 binary tree.

题目中文

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
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){return Find(root, p, q);}private TreeNode Find(TreeNode current, TreeNode p, TreeNode q){if (current == null || current == p || current == q)return current;TreeNode left = Find(current.left, p, q);TreeNode right = Find(current.right, p, q);if (left != null && right != null)return current;return left != null ? left : right;}
}

实验结果

状态：通过
31 / 31 个通过测试用例
执行用时: 132 ms, 在所有 C# 提交中击败了 96.10% 的用户
内存消耗: 27.5 MB, 在所有 C# 提交中击败了 20.00% 的用户

提交结果

学习UI设计都需要了解哪些知识

由于UI设计的高薪，很多人都萌生了想要学习UI设计的想法，但是小编提醒大家，学习UI设计之前一定要做足功课，了解UI设计基本知识，再看看自己是否适合学习，下面小编就为大家详细的介绍一下学习UI设计都需要了解…

编程日记2024/09/27 12:10:00

Marty Cagan：怎样寻找出色的产品经理

《程序员杂志》的文章，原帖位于http://www.programmer.com.cn/7760/ 写的很好，自己转贴存储一下，也符合Product Owner的要求，就是……要求太高了！本文是他回顾自己二十多年来从事软件产品管理工作的总结和经验分享&…

编程日记2024/09/27 12:00:00

LeetCode实战：除自身以外数组的乘积

背景为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given an array nums of n integers where n > 1, return an array output such that ou…

编程日记2024/09/27 11:50:00

PHP+MySql获取自动增长字段的新添加记录ID值

PHPMySql获取新添加记录的ID值 1.假设字段名称为recordID 2.字段属性须设为：auto_increment 3.添加数据后使用 $newID mysql_insert_id(); 得到ID值 ASP获取即时ID值 ASPAccess2000 1.要获取的ID值字段属性必须设为：自动编号(我们假设字段名为recordID)…

编程日记2024/09/27 11:40:00

MyBatis框架添加客户有哪些步骤

在MyBatis的映射文件中，添加操作是通过元素来实现的。例如，向数据库中的t_customer表中插入一条数据可以通过如下配置来实现。在上述配置代码中，传入的参数是一个Customer类型，该类型的参数对象被传递到语句中时，#{us…

编程日记2024/09/27 11:30:00

磁盘IO的总结

转自：http://simpleframework.net/blog/v/8486.html 1. 完全随机写还是跳跃，5倍的性能差距！ 全随机写无疑是最慢的写入方式，在logic dump测试中很惊讶的发现，将200M的内存数据随机的写入到100G的磁盘数据里面&#xf…

编程日记2024/09/27 11:20:00

UI设计培训之设计中的点线面-面

想要学好UI设计，从事UI设计工作，那么理论基础知识一定要会，今天小编为大家整理的就是关于UI设计中的点线面-面，在平面构成三要素中面是相对占空间最大的元素，在设计中也包含和表现更加强烈的情感色彩，有明显…

编程日记2024/09/27 11:10:00

projecteuler_problem10

problem10 地址：https://projecteuler.net/problem10。源码：gitcode.aliyun.com:qianlizhixing12/ProjectEuler.git。问题：找到2000000内质数和。 #include <stdio.h> #include <math.h> #include "debug.h" #include…

编程日记2024/09/27 11:00:00

LeetCode实战：排序链表

背景为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Sort a linked list in O(n log n) time using constant space complexity. Example 1: I…

编程日记2024/09/27 10:50:00

技术图文：双指针在链表问题中的应用

背景最近这段时间团队在进行算法刻意练习活动，我带着同学们刷 leetcode 的“腾讯精选练习（50）题”，参见：我是如何组织“算法刻意练习活动”的？ 在做题的过程中，同学们讨论比较多的是链表中遇…

编程日记2024/09/27 10:40:00

[BuildRelease]build number / id

build number， 也称为build id， 在build release的流程中唯一标示一个build，也是正式的产品的product version 和file version后两位（Major.minor.xxx.xxx）的来源，可以使用合适的方法将build number转化到p…

编程日记2024/09/27 10:30:00

Windows Azure Storage (25) Azure Append Blob

《Windows Azure Platform 系列文章目录》在笔者之前的文章中，我们介绍了Azure Blob 有两种：Block Blob和Page Blob。在这里笔者介绍Blob的第三种：Append Blob。概念： 1.Append Blob概念类似于Block Blob，因为都是由…

编程日记2024/09/27 10:20:00

学python培训到底能干嘛

Python是在人工智能领域发挥着很重要的作用的，现在依旧有很多人对Python这项技术不是很了解，学Python培训到底能干嘛?下面小编来为大家做下详细的介绍。 python其实并不难学，对于初学者和完成普通任务，Python语言是非常简单易用的…

编程日记2024/09/27 10:10:00

使用VB.NET加快代码开发速度

以前在学校时，编写代码都是使用C#，习惯了C#的代码习惯，等工作后由于工作需要逐渐的开始采用了VB.NET开发项目，渐渐地喜欢上了VB.NET，现在我就罗列一些VB.NET加速代码开发的方法。一、智能感知做.NET开发的许多人都知…

编程日记2024/09/27 10:00:00

技术图文：举例详解Python中 split() 函数的使用方法

背景这篇文章主要介绍Python中的split()函数的使用方法，split()函数通常用于将字符串切片并转换为列表，需要的朋友可以参考一下。技术分析 Python中有split()和os.path.split()两个函数，具体作用如下： split()：拆…

编程日记2024/09/27 09:50:00

Burning

转载于:https://www.cnblogs.com/kuiyuan/archive/2011/09/02/2163621.html

编程日记2024/09/27 09:40:00

UI设计工作好找吗?有哪些面试技巧?

最近有很多学习UI设计的学员，想要了解UI设计学成之后是否好找工作?对于后期的面试有哪些技巧?下面小编整理的这些希望可以帮助到大家，来看看下面的详细介绍。 UI设计工作好找吗?有哪些面试技巧? 作品：很多初级小白的问题所在就是缺少大量…

编程日记2024/09/27 09:30:00

刻意练习：Python基础 -- Task10. 类与对象

背景我们准备利用17天时间，将 “Python基础的刻意练习” 分为如下任务： Task01：变量、运算符与数据类型（1day）Task02：条件与循环（1day）Task03：列表与元组（…

编程日记2024/09/27 09:20:00

CentOS 7更新时出现Multilib version problems

这两天在更新CentOS7系统时，出现了Multilib version problems错误，执行命令： # yum update 出现了的错误信息： .... ---> Package libcap-ng.i686 0:0.7.5-4.el7 will be installed ---> Package libstdc.i686 0:4.8.5-16.e…

编程日记2024/09/27 09:10:00

HTTP 错误 404.13 - Not Found 请求筛选模块被配置为拒绝超过请求内容长度的请求。...

把以下内容加在web.config的<system.webServer>节点 <security><requestFiltering ><requestLimits maxAllowedContentLength"1024000000" ></requestLimits></requestFiltering></security> 上述中maxAllowedContentLeng…

编程日记2024/09/27 09:00:00