剑指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限制：
0 <= 节点个数 <= 10000解题：
- 首先要遍历A找出与B根节点一样值的节点R
- 然后判断树A中以R为根节点的子树是否包含和B一样的结构
- 注意：空树不是任意一个树的子结构
/*** 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:bool isSubStructure(TreeNode* A, TreeNode* B) {bool res = false;//当TreeA和TreeB都不为零的时候，才进行比较。否则直接返回falseif (A!=NULL && B!=NULL){//如果找到了对应TreeB的根节点的点if (A->val == B->val)//以这个根节点为为起点判断是否包含TreeBres = helper(A, B);//如果找不到，那么就再去TreeA的左子树当作起点，去判断是否包含TreeBif (!res)res = isSubStructure(A->left, B);//如果还找不到，那么就再去TreeA的右子树当作起点，去判断是否包含TreeBif (!res)res = isSubStructure(A->right, B);}// 返回结果return res;}bool helper(TreeNode* A, TreeNode* B){//如果TreeB已经遍历完了都能对应的上，返回trueif (B==NULL)return true;//如果TreeB还没有遍历完，TreeA却遍历完了。返回falseif (A==NULL)return false;//如果其中有一个点没有对应上，返回falseif (A->val != B->val)return false;//如果根节点对应的上，那么就分别去子节点里面匹配return helper(A->left, B->left) && helper(A->right, B->right);}
};简化代码：
class Solution {
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if (A == NULL || B == NULL) {return false;}return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);}bool helper(TreeNode* A, TreeNode* B) {if (A == NULL || B == NULL) {return B == NULL ? true : false;}if (A->val != B->val) {return false;}return helper(A->left, B->left) && helper(A->right, B->right);}
};
https://www.jianshu.com/p/a04d73417f7c
更多相关：
-
题目：从上到下打印二叉树 II 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [9,20], [...
-
题目：对称的二叉树 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / 2 2 / / 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:...
-
题目：二叉树的镜像 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 4 / 2 7 / / 1 3 6 9 镜像输出： 4 / 7 2 / / 9 6 3 1 示例 1： 输入：root =...
-
下面是树类型题目需要用到的头文件tree.h,请包含在cpp文件中编译,而不是放在c文件中编译,比如查找树中两个节点的最低公共父结点的题common_parent_in_tree.cpp,编译它的方法是: g++ -g common_parent_in_tree.cpp -o common_parent_in_tree 下...
-
在使用空时，习惯这么赋值 int *p = NULL; 编译器进行解释程序时，NULL会被直接解释成0，所以这里的参数根本就不是大家所想的NULL，参数已经被编译器偷偷换成了0，0是整数。 因此这面的问题就尴尬了 不好意思图片引用于网络中。 为啥呢不是this is the ptr function…这个。这就是C++中的...
-
var d= {a: 1,b: null,c: 3,d: undefined };Object.keys(d).forEach(k=>d[k]==null&&delete d[k]);//去掉值为null或undefined的对象属性//Object.keys(d).forEach(k=>(d[k]==null||d[k]==='')...
-
//ES6获取浏览器url跟参 public getUrlParam = a => (a = location.search.substr(1).match(new RegExp(`(^|&)${a}=([^&]*)(&|$)`)),a?a[2]:null);...
-
文章目录1. 解决问题2. 应用场景3. 实现如下C++实现C语言实现4. 缺点 1. 解决问题 在简单工厂模式中，我们使用卖衣服进行举例，同一种工厂可以卖很多不同种类的衣服，工厂只是将衣服的生产过程进行了封装。 当我们增加衣服种类的时候，在简单工厂模式中需要修改工厂的代码，破坏了类的开闭原则（对扩展开发， 对修改关闭），...
-
在服务端数据库的处理当中，涉及中文字符的结构体字段，需要转为Utf8后再存储到表项中。从数据库中取出包含中文字符的字段后，如果需要保存到char *类型的结构体成员中，需要转为Ansi后再保存。从数据库中取出类型数字的字段后，如果需要保存到int型的结构体成员中，需要调用atoi函数进行处理后再保存。 1 static char *...
-
/*判断屏幕宽高比是否为16:9*/ function isScreen16to9() {return window.screen.height / window.screen.width === 9 / 16; }...
-
/*关闭、刷新、跳转、离开当前网页前提示*/ onbeforeunload = function () {return false; }; ...
-
let json = {/**判断JSON格式*/ isJSON: function (str) {if (typeof str == "string") {try {var obj = JSON.parse(str);if (typeof obj == "object" && obj) {return true;} else {...
-
项目结构 index.js //必须要安装否则就别想运行了❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤ //npm i body-parser -D & cnpm i express & cnpm i node-xlsx & cnp...
-
一、递归 函数 为什么要有函数，提高代码的可读性，避免重复的代码，提高代码的复用性 在函数中能用return的不要print 1、递归的最大深度997 def foo(n):print(n)n+=1foo(n) foo(1) 递归的最大深度 2、修改递归的最大深度 由此我们可以看出，未报错之前能看到的最大数...