当前位置:网站首页>Leetcode exercise - Sword finger offer 26 Substructure of tree
Leetcode exercise - Sword finger offer 26 Substructure of tree
2022-07-06 22:26:00 【SK_ Jaco】
1. Title Description
The finger of the sword Offer 26. The substructure of a tree
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
2. Problem solving ideas and codes
2.1 Their thinking
Question request judgment B Is it A The subtree of , So first we need to be in A Find B Root node of , Then start from the root node to judge whether the nodes are the same . So the topic becomes two steps : stay A Search for B Root node of the same node 、 Take this node as the root node and B Compare and judge whether they are the same in turn . Take the topic as an example 2 To illustrate .
First, in the A Find and B Points with the same root node value
stay A After finding the node in , Take this node as the root node and B Compare from the root node , until B Traverse complete
It should be noted that , The values of nodes in the title may be the same , So you need to A Find each node , And make a comparison every time you find one .
2.2 Code
class Solution {
boolean ans = false;
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null) {
return false;
}
find(A, B);
return ans;
}
// Compare whether the two trees are the same
public boolean compare(TreeNode root, TreeNode compareNode) {
if (root == null) {
return compareNode == null;
}
if (compareNode == null) {
return true;
}
if (root.val != compareNode.val) {
return false;
}
// Compare the leftmost subtree of the current node
boolean p1 = compare(root.left, compareNode.left);
// Compare the right subtree of the current node
boolean p2 = compare(root.right, compareNode.right);
return p1 & p2;
}
public void find(TreeNode root, TreeNode compareNode) {
if (root == null) {
return;
}
if (root.val == compareNode.val) {
// When the value of the current node is the same as that of the tree head node for comparison , Compare
boolean compare = compare(root, compareNode);
ans |= compare;
}
// Find the left subtree
find(root.left, compareNode);
// Find the right subtree
find(root.right, compareNode);
}
}
2.3 test result
Pass the test
3. summary
- According to the requirements of the topic, we need to search and compare the tree
- Every time you find a node with the same value, you need to make a comparison
边栏推荐
- Senior soft test (Information System Project Manager) high frequency test site: project quality management
- 重磅新闻 | Softing FG-200获得中国3C防爆认证 为客户现场测试提供安全保障
- return 关键字
- Learn the principle of database kernel from Oracle log parsing
- 中国VOCs催化剂行业研究与投资战略报告(2022版)
- BarcodeX(ActiveX打印控件) v5.3.0.80 免费版使用
- C # réalise la liaison des données du rapport Crystal et l'impression du Code à barres 4
- 414. The third largest digital buckle
- Search element topic (DFS)
- HDR image reconstruction from a single exposure using deep CNNs阅读札记
猜你喜欢
Assembly and interface technology experiment 5-8259 interrupt experiment
C#实现水晶报表绑定数据并实现打印4-条形码
Management background --4, delete classification
Learn the principle of database kernel from Oracle log parsing
Powerful domestic API management tool
LeetCode刷题(十一)——顺序刷题51至55
[10:00 public class]: basis and practice of video quality evaluation
自制J-Flash烧录工具——Qt调用jlinkARM.dll方式
labelimg的安装与使用
About the professional ethics of programmers, let's talk about it from the way of craftsmanship and neatness
随机推荐
Attack and defense world miscall
图像的spatial domain 和 frequency domain 图像压缩
中国固态氧化物燃料电池技术进展与发展前景报告(2022版)
空结构体多大?
PVL EDI 项目案例
MySQL约束的分类、作用及用法
C # réalise la liaison des données du rapport Crystal et l'impression du Code à barres 4
Management background --5, sub classification
Web APIs DOM 时间对象
HDU 4912 paths on the tree (lca+)
HDR image reconstruction from a single exposure using deep CNNs阅读札记
硬件開發筆記(十): 硬件開發基本流程,制作一個USB轉RS232的模塊(九):創建CH340G/MAX232封裝庫sop-16並關聯原理圖元器件
go多样化定时任务通用实现与封装
Report on technological progress and development prospects of solid oxide fuel cells in China (2022 Edition)
CCNA Cisco network EIGRP protocol
extern关键字
What a new company needs to practice and pay attention to
Management background --3, modify classification
Installation and use of labelimg
Senior soft test (Information System Project Manager) high frequency test site: project quality management