给你两棵二叉树 root 和 subRoot 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它服务器托管网自身的一棵子树
输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool compare (struct TreeNode* p1,struct TreeNode* p2)
{
if(!p1&&!p2) return true;
if(!p1||!p2) return false;
if(p1->val!=p2->val) return false;
return compare(p1->left,p2->left)&&compare(p1服务器托管网->right,p2->right);
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t){
if(!s) return false;
return compare(s,t)||isSubtree(s->left,t)||isSubtree(s->right,t);
}
首先:compare函数是比较两棵树是否相等的函数,因为如果一棵树是另一棵树的子树,那么必定存在这棵树和另一棵树的子树相等。而compare函数利用了遍历树的常规思路——递归
首先比较根节点,若根节点同时为空,则两树相等。
若其中一个为空,另一个非空,则两树不等。
若节点上的数值不等,则两树不等。
剩下的就是,节点上的数值相等,进而要向下比较它们的子树是否相等,使用递归,分别比较左右子树是否相等,注意:一定要都相等才可以
接下来,isSubtree函数也是利用了递归的思想写出来的,
如果递归到最后,s都已经为空了,那么再无相等可言,return false;
否则的话,按照根左右的方法来进行比较,由递归可知,只要存在完全相等的部分,函数的返回值就是真的
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: Revit中用自适应创建简单的瓦片族和切换构件的材质?
一、Revit中使用自适应创建瓦片族 在我们的日常生活中,屋顶的瓦片是我们经常都能够见到的,瓦片能够挡风遮雨也能够使建筑物带来古香古色的气息,那我们今天来学习如何使用自适应创建简单的瓦片族。 1.首先:我们打开自适应公制常规模型族制作一片瓦的族,设…