当前位置:网站首页>Leetcode skimming: binary tree 25 (the nearest common ancestor of binary search tree)
Leetcode skimming: binary tree 25 (the nearest common ancestor of binary search tree)
2022-07-07 12:47:00 【Taotao can't learn English】
235. The nearest common ancestor of a binary search tree
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 .
This problem can also be done by using the general method in my last section , It's just a binary search tree , Orderly , It can be done according to the nature . nature : Orderly ( The decreasing )
package com.programmercarl.tree;
/** * @ClassName BstLowestCommonAncestor * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 12:36 * @Version 1.0 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ * 235. The nearest common ancestor of a binary search tree **/
public class BstLowestCommonAncestor {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Because it's orderly , Just find the node closest to the two elements
// The template node is on the left of the current node
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
//root Between the two nodes , It's a closed interval . And it's [p,q] The closed interval of , No p Namely q
// Because it moves step by step , So it's the critical point
return root;
}
return lowestCommonAncestor(root, p, q);
}
}
边栏推荐
- 有什么类方法或是函数可以查看某个项目的Laravel版本的?
- The left-hand side of an assignment expression may not be an optional property access. ts(2779)
- 【从 0 开始学微服务】【02】从单体应用走向服务化
- [statistical learning method] learning notes - logistic regression and maximum entropy model
- [Q&A]AttributeError: module ‘signal‘ has no attribute ‘SIGALRM‘
- 【PyTorch实战】图像描述——让神经网络看图讲故事
- 2022 examination questions and online simulation examination for safety production management personnel of hazardous chemical production units
- 2022广东省安全员A证第三批(主要负责人)考试练习题及模拟考试
- Dialogue with Wang Wenyu, co-founder of ppio: integrate edge computing resources and explore more audio and video service scenarios
- 2022A特种设备相关管理(锅炉压力容器压力管道)模拟考试题库模拟考试平台操作
猜你喜欢
The left-hand side of an assignment expression may not be an optional property access. ts(2779)
How to use PS link layer and shortcut keys, and how to do PS layer link
In the small skin panel, use CMD to enter the MySQL command, including the MySQL error unknown variable 'secure_ file_ Priv 'solution (super detailed)
MPLS experiment
[statistical learning methods] learning notes - Chapter 5: Decision Tree
Day-19 IO stream
Static routing assignment of network reachable and telent connections
Ctfhub -web SSRF summary (excluding fastcgi and redI) super detailed
About IPSec
Experiment with a web server that configures its own content
随机推荐
[疑难杂症]pip运行突然出现ModuleNotFoundError: No module named ‘pip‘
Attack and defense world - PWN learning notes
Pule frog small 5D movie equipment | 5D movie dynamic movie experience hall | VR scenic area cinema equipment
In the small skin panel, use CMD to enter the MySQL command, including the MySQL error unknown variable 'secure_ file_ Priv 'solution (super detailed)
2022 practice questions and mock examination of the third batch of Guangdong Provincial Safety Officer a certificate (main person in charge)
SQL Lab (46~53) (continuous update later) order by injection
[Q&A]AttributeError: module ‘signal‘ has no attribute ‘SIGALRM‘
[deep learning] image multi label classification task, Baidu paddleclas
test
Day-20 file operation, recursive copy, serialization
[pytorch practice] use pytorch to realize image style migration based on neural network
【PyTorch实战】用RNN写诗
Session
SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
Connect to blog method, overload, recursion
NPM instal reports agent or network problems
浅谈估值模型 (二): PE指标II——PE Band
Master formula. (used to calculate the time complexity of recursion.)
Static comprehensive experiment
Sorting, dichotomy