当前位置:网站首页>Sword finger offer 26 Substructure of tree
Sword finger offer 26 Substructure of tree
2022-07-07 00:11:00 【xzystart】
Input two binary trees A and B, Judge B Is it right? A Substructure of .( A convention empty tree is not a substructure of any tree )
B yes A Substructure of , namely A There are emergence and B Same structure and node values .
for example :
Given tree A:
3
/ \
4 5
/ \
1 2
Given tree B:
4
/
1
return true, because B And A A subtree of has the same structure and node values .
Example 1:
Input :A = [1,2,3], B = [3,1]
Output :false
Example 2:
Input :A = [3,4,5,1,2], B = [4,1]
Output :true
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// Judge by ab A tree for roots b Whether it is a Substructure of
// The function of this function is to judge the two trees of the input parameter ,b Whether it is a Substructure of
// The principle is to see a Whether or not b Exactly the same , If the same returns true, If not, judge a Whether the left and right subtrees of are related to b Exactly the same ,
// The principle is to find A A child node of the tree ( Contains the root node ) Is the subtree of the root and B The trees are exactly equal , If this condition is met , It can be said that it meets the meaning of the topic
// If traversal to empty has not found , It proves that the meaning of the question is not satisfied
if (B == null || A == null) {
// Special value judgment ( Recursion to empty has not been found through the following if)
return false;
}
if (A.val == B.val && (helper(A.left, B.left) && helper(A.right, B.right))) {
// Judge ab Is it completely equal
return true; // There is only one recursive function true return , So the top function is true( Because recursion uses the or operator )
}
// Recursively call ( If the above if If you pass, you will not enter here. Enter here to explain ab A tree with roots does not meet the condition )
// If the above if Pass to prove B Trees and A The molecular structure of a part of the tree is completely equal
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
// Use the or operator , As long as there is one satisfaction, it will be satisfied as a whole
}
private boolean helper(TreeNode root1, TreeNode root2) {
// Judge by ab Whether the trees with roots are completely equal
// Be careful , The function of this function is to judge whether the two trees of the input parameter are completely equal
if (root2 == null) {
return true;
}
if (root1 == null) {
return false;
}
if (root1.val == root2.val) {
return helper(root1.left, root2.left) && helper(root1.right, root2.right);
} else {
return false;
}
}
}
边栏推荐
- Design of short chain
- 氢创未来 产业加速 | 2022氢能专精特新创业大赛报名通道开启!
- 快手的新生意,还得靠辛巴吆喝?
- Please help xampp to do sqlilab is a black
- DAY FIVE
- 服务器SMP、NUMA、MPP体系学习笔记。
- DAY TWO
- MATLIB从excel表中读取数据并画出函数图像
- How can computers ensure data security in the quantum era? The United States announced four alternative encryption algorithms
- 陀螺仪的工作原理
猜你喜欢
Cas d'essai fonctionnel universel de l'application
陀螺仪的工作原理
Introduction au GPIO
app通用功能測試用例
ldap创建公司组织、人员
2022 latest blind box mall complete open source operation source code / docking visa free payment interface / building tutorial
[OFDM communication] OFDM system signal detection based on deep learning with matlab code
DAY FIVE
Tourism Management System Based on jsp+servlet+mysql framework [source code + database + report]
Wind chime card issuing network source code latest version - commercially available
随机推荐
AVL树到底是什么?
Use type aliases in typescript
Compile logisim
17、 MySQL - high availability + read / write separation + gtid + semi synchronous master-slave replication cluster
陀螺仪的工作原理
DAY FIVE
Google, Baidu and Yahoo are general search engines developed by Chinese companies_ Baidu search engine URL
Oracle中使用包FY_Recover_Data.pck来恢复truncate误操作的表
【自动化测试框架】关于unittest你需要知道的事
三句话简要介绍子网掩码
[OFDM communication] OFDM system signal detection based on deep learning with matlab code
2022 latest blind box mall complete open source operation source code / docking visa free payment interface / building tutorial
Scholar doctor hahaha
[212] what are three methods for PHP to send post requests
Wasserstein slim gain with gradient poverty (wsgain-gp) introduction and code implementation -- missing data filling based on generated countermeasure network
[system analyst's road] Chapter 7 double disk system design (service-oriented development method)
PDF文档签名指南
谷歌百度雅虎都是中国公司开发的通用搜索引擎_百度搜索引擎url
微信小程序uploadfile服务器,微信小程序之wx.uploadFile[通俗易懂]
DAY TWO