当前位置:网站首页>LeetCode 练习——剑指 Offer 26. 树的子结构
LeetCode 练习——剑指 Offer 26. 树的子结构
2022-07-06 14:31:00 【SK_Jaco】
1.题目描述
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B:
4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
2.解题思路与代码
2.1 解题思路
题目要求判断 B 是否为 A 的子树,那么首先我们就需要在 A 中找到 B 的根结点,然后从根节点开始以此判断节点是否相同。因此题目就变成了两个步骤:在 A 中寻找 B 的根结点相同的节点、以该节点为根结点和 B 依次比较判断是否相同。以题目示例 2 进行图解。
首先在 A 中寻找和 B 根结点值相同的点
在 A 中找到节点以后,以该节点为根结点与 B 从根节点开始进行比较,直到 B 遍历完成
需要注意的是,题目中节点的值可能相同,因此需要对 A 每个节点进行查找,并且每查找到一个就进行一次比较。
2.2 代码
class Solution {
boolean ans = false;
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null) {
return false;
}
find(A, B);
return ans;
}
// 比较两个树是否相同
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;
}
// 比较当前节点的最左子树
boolean p1 = compare(root.left, compareNode.left);
// 比较当前节点的右子树
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) {
// 当前节点的值与进行比较的树头节点值相同时,进行比较
boolean compare = compare(root, compareNode);
ans |= compare;
}
// 查找左子树
find(root.left, compareNode);
// 查找右子树
find(root.right, compareNode);
}
}
2.3 测试结果
通过测试
3.总结
- 按照题目要求需要对树进行查找和比较两个过程
- 每查找到一次相同值节点就需要进行一次比较
边栏推荐
- Oracle-控制文件及日志文件的管理
- Lora sync word settings
- Notes de développement du matériel (10): flux de base du développement du matériel, fabrication d'un module USB à RS232 (9): création de la Bibliothèque d'emballage ch340g / max232 SOP - 16 et Associa
- i.mx6ull搭建boa服务器详解及其中遇到的一些问题
- GD32F4XX串口接收中断和闲时中断配置
- anaconda安装第三方包
- 3DMax指定面贴图
- Four data streams of grpc
- GPS from getting started to giving up (12), Doppler constant speed
- PVL EDI 项目案例
猜你喜欢
Common sense: what is "preservation" in insurance?
Assembly and interface technology experiment 5-8259 interrupt experiment
The nearest common ancestor of binary (search) tree ●●
NetXpert XG2帮您解决“布线安装与维护”难题
GPS从入门到放弃(十六)、卫星时钟误差和卫星星历误差
Embedded common computing artifact excel, welcome to recommend skills to keep the document constantly updated and provide convenience for others
3DMax指定面贴图
GPS from getting started to giving up (16), satellite clock error and satellite ephemeris error
Mise en place d'un environnement de développement OP - tee basé sur qemuv8
[linear algebra] determinant of order 1.3 n
随机推荐
Attack and defense world ditf Misc
i. Mx6ull build boa server details and some of the problems encountered
GNN, please deepen your network layer~
GPS from getting started to giving up (XIII), receiver autonomous integrity monitoring (RAIM)
GPS從入門到放弃(十三)、接收機自主完好性監測(RAIM)
Unity3d Learning Notes 6 - GPU instantiation (1)
Chapter 4: talk about class loader again
[leetcode daily clock in] 1020 Number of enclaves
ResNet-RS:谷歌领衔调优ResNet,性能全面超越EfficientNet系列 | 2021 arxiv
数据处理技巧(7):MATLAB 读取数字字符串混杂的文本文件txt中的数据
What a new company needs to practice and pay attention to
[sdx62] wcn685x will bdwlan Bin and bdwlan Txt mutual conversion operation method
C # réalise la liaison des données du rapport Crystal et l'impression du Code à barres 4
Embedded common computing artifact excel, welcome to recommend skills to keep the document constantly updated and provide convenience for others
Applet system update prompt, and force the applet to restart and use the new version
Build op-tee development environment based on qemuv8
Research and investment strategy report of China's VOCs catalyst industry (2022 Edition)
2022-07-05 使用tpcc对stonedb进行子查询测试
Kohana 数据库
GPS from getting started to giving up (XX), antenna offset