当前位置:网站首页>[daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree
[daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree
2022-07-07 05:49:00 【Puppet__】
subject
Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .
In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
for example , Given the following 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
explain : node 2 And nodes 8 The most recent public ancestor of 6.
Example 2:
Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output : 2
explain : node 2 And nodes 4 The most recent public ancestor of 2, Because by definition, the nearest common ancestor node can be the node itself .
explain :
The values of all nodes are unique .
p、q For different nodes and all exist in a given binary search tree .
Code
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// At the same time, find the arrival p、q The path of , Find the bifurcation point of two paths , Make full use of the properties of binary search tree
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode ansNode = root;
while(true){
if(p.val < ansNode.val && q.val < ansNode.val){
ansNode = ansNode.left;
}
else if(p.val > ansNode.val && q.val > ansNode.val){
ansNode = ansNode.right;
}
// The path forked , This point is the nearest common ancestor
else{
break;
}
}
return ansNode;
}
}
边栏推荐
- AI人脸编辑让Lena微笑
- Educational Codeforces Round 22 B. The Golden Age
- Red Hat安装内核头文件
- 微信小程序蓝牙连接硬件设备并进行通讯,小程序蓝牙因距离异常断开自动重连,js实现crc校验位
- 【日常训练--腾讯精选50】292. Nim 游戏
- The navigation bar changes colors according to the route
- [shell] clean up nohup Out file
- Input of native applet switches between text and password types
- I didn't know it until I graduated -- the principle of HowNet duplication check and examples of weight reduction
- Web authentication API compatible version information
猜你喜欢
ForkJoin最全详解(从原理设计到使用图解)
《2022中国低/无代码市场研究及选型评估报告》发布
Digital innovation driven guide
Unity keeps the camera behind and above the player
Paper reading [open book video captioning with retrieve copy generate network]
Get the way to optimize the one-stop worktable of customer service
Randomly generate session_ id
软件测试面试技巧
R language [logic control] [mathematical operation]
论文阅读【Open-book Video Captioning with Retrieve-Copy-Generate Network】
随机推荐
集群、分布式、微服务的区别和介绍
Mysql-centos7 install MySQL through yum
淘宝商品详情页API接口、淘宝商品列表API接口,淘宝商品销量API接口,淘宝APP详情API接口,淘宝详情API接口
Modes of optical fiber - single mode and multimode
淘宝店铺发布API接口(新),淘宝oAuth2.0店铺商品API接口,淘宝商品发布API接口,淘宝商品上架API接口,一整套发布上架店铺接口对接分享
Reptile exercises (III)
AI face editor makes Lena smile
【已解决】记一次EasyExcel的报错【读取xls文件时全表读不报错,指定sheet名读取报错】
分布式事务解决方案之2PC
高级程序员必知必会,一文详解MySQL主从同步原理,推荐收藏
Codeforces Round #416 (Div. 2) D. Vladik and Favorite Game
2pc of distributed transaction solution
Five core elements of architecture design
C nullable type
980. 不同路径 III DFS
JVM the truth you need to know
力扣102题:二叉树的层序遍历
Hcip seventh operation
Hcip eighth operation
zabbix_get测试数据库失败