药业集团网站策划方案范文,浙江电信关于网站备案信息核实的公告,网站网站开发逻辑,wordpress 新闻页面题目
给定两个非空二叉树 s 和 t#xff0c;检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1: 给定的树 s: 示例 2: 给定的树 s:
思路
思路#xff1a;首先层序遍历s树…题目
给定两个非空二叉树 s 和 t检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1: 给定的树 s: 示例 2: 给定的树 s:
思路
思路首先层序遍历s树如果遇到结点值和t根结点值相同的开始比较以该结点为根结点的树与t树是否相同。 这里有一些点需要注意 1、s树中可能有许多结点的值和t根结点值相同所以我们应该对每次比较的结果做记录如果有相同则直接返回true否则必须等所有结点都遍历之后。 2、这一题用的比较两棵树是否相同的函数来源于这一题 LeetCode 100. 相同的树 思考分析
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {//如果两个结点存在if(p q){//如果两个结点值相同观察他们的左右子树是否同时相同if(p-val q-val){return isSameTree(p-right,q-right) isSameTree(p-left,q-left);}//如果两个结点值不同说明树不相同else{return false;} }//如果两个结点同时不存在那么树相同else if(!p !q){return true;}//如果一个树有此结点而另外一棵树没有此结点则说明结构不同return false;}bool isSubtree(TreeNode* s, TreeNode* t) {queueTreeNode* que;bool result false;int right_times0;if(s!NULL) que.push(s);while(!que.empty()){int size que.size();for(int i 0;isize;i){TreeNode* node que.front();que.pop();if(node-val t-val){result isSameTree(node,t);if(result true) right_times; if(right_times0) return true;}//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}}return false;}
};看了一下官方题解第一个思路应该是和我差不多的判断子树是否相同都用的深度不过一开始寻找相同结点我使用的是广度
class Solution {
public:bool check(TreeNode *o, TreeNode *t) {if (!o !t) {return true;}if ((o !t) || (!o t) || (o-val ! t-val)) {return false;}return check(o-left, t-left) check(o-right, t-right);}bool dfs(TreeNode *o, TreeNode *t) {if (!o) {return false;}return check(o, t) || dfs(o-left, t) || dfs(o-right, t);}bool isSubtree(TreeNode* s, TreeNode* t) {return dfs(s,t);}
};后面的两个由于还没有学到相关知识暂时先搁置。 另一个树的子树
