兼职做效果图的网站有哪些,wordpress搜索框插件,做外贸企业网站要注意哪些,网站特效怎么做自适应给你两棵二叉树 root 和 subRoot 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子…
给你两棵二叉树 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 否则的话按照根左右的方法来进行比较由递归可知只要存在完全相等的部分函数的返回值就是真的