当前位置:网站首页>leetcode:236. The nearest common ancestor of binary tree
leetcode:236. The nearest common ancestor of binary tree
2022-07-06 23:33:00 【uncle_ ll】
236. The nearest common ancestor of a binary tree
source : Power button (LeetCode)
link : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
Given a binary 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, The nearest 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 ).”
Example 1:
Input :root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output :3
explain : node 5 And nodes 1 The most recent public ancestor of is the node 3 .
Example 2:
Input :root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output :5
explain : node 5 And nodes 4 The most recent public ancestor of is the node 5 . Because by definition, the nearest common ancestor node can be the node itself .
Example 3:
Input :root = [1,2], p = 1, q = 2
Output :1
Tips :
- The number of nodes in the tree is in the range [2, 1 0 5 10^5 105] Inside .
- − 1 0 9 -10^9 −109 <= Node.val <= 1 0 9 10^9 109
- all Node.val Different from each other .
- p != q
- p and q All exist in a given binary tree .
solution
- recursive : Start with the root node , If the root node is empty , Or a search element is the root node , Directly back to the root node ; Then recursively find the left subtree , Right subtree , If the search results of both subtrees are not empty , indicate p,q The two elements to be found are the same as the root node of the left subtree or the root node of the right subtree , Then the common node of the two is the root node of the tree ; If the search of a subtree is empty , Then return the search result of another subtree ;
Code implementation
recursive
python Realization
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return root
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # The search results of the two subtrees are not empty , Description shot ,
return root
return left if left else right
c++ Realization
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr)
return root;
if (p == root || q == root)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr)
return root;
return left != nullptr ? left : right;
}
};
Complexity analysis
- Time complexity : O ( N ) O(N) O(N)
- Spatial complexity : O ( N ) O(N) O(N)
边栏推荐
- Station B boss used my world to create convolutional neural network, Lecun forwarding! Burst the liver for 6 months, playing more than one million
- (1) Chang'an chain learning notes - start Chang'an chain
- 华为云GaussDB(for Redis)揭秘第21期:使用高斯Redis实现二级索引
- How much does the mlperf list weigh when AI is named?
- Experiment 5: common automation libraries
- js导入excel&导出excel
- Two week selection of tdengine community issues | phase II
- koa2对Json数组增删改查
- Up to 5million per person per year! Choose people instead of projects, focus on basic scientific research, and scientists dominate the "new cornerstone" funded by Tencent to start the application
- Knowledge * review
猜你喜欢
浅谈现在的弊端与未来的发展
Cover fake big empty talk in robot material sorting
Today's sleep quality record 78 points
Coscon'22 community convening order is coming! Open the world, invite all communities to embrace open source and open a new world~
Koa2 addition, deletion, modification and query of JSON array
[launched in the whole network] redis series 3: high availability of master-slave architecture
Gradle知識概括
(shuttle) navigation return interception: willpopscope
B 站弹幕 protobuf 协议还原分析
电脑重装系统u盘文件被隐藏要怎么找出来
随机推荐
What does front-end processor mean? What is the main function? What is the difference with fortress machine?
让 Rust 库更优美的几个建议!你学会了吗?
Experiment 4: installing packages from Gui
Station B Big utilise mon monde pour faire un réseau neuronal convolutif, Le Cun Forward! Le foie a explosé pendant 6 mois, et un million de fois.
MySQL实现字段分割一行转多行的示例代码
Modules that can be used by both the electron main process and the rendering process
js对JSON数组的增删改查
The programmer said, "I'm 36 years old, and I don't want to be rolled, let alone cut."
flinksql select id ,count(*) from a group by id .
[launched in the whole network] redis series 3: high availability of master-slave architecture
PDF批量拆分、合并、书签提取、书签写入小工具
士大夫哈哈哈
请问oracle-cdc用JsonDebeziumDeserializationSchema反序列化
【系统分析师之路】第七章 复盘系统设计(面向服务开发方法)
MySQL数据库之JDBC编程
A novice asks a question. I am now deployed on a single machine. I submitted an SQL job and it runs normally. If I restart the service job, it will disappear and I will have to
NFTScan 开发者平台推出 Pro API 商业化服务
If the request URL contains jsessionid, the solution
mysql-cdc 的jar包 ,在flink运行模式下,是不是要放在不同的地方呢?
Without CD, I'll teach you a trick to restore the factory settings of win10 system