学校网站建设成功,大型电商网站开发价格,英文网站建设哪家强,备案 网站大家好#xff0c;我是苏貝#xff0c;本篇博客带大家刷题#xff0c;如果你觉得我写的还不错的话#xff0c;可以给我一个赞#x1f44d;吗#xff0c;感谢❤️ 目录 一. 相同的树二. 对称二叉树三. 另一棵树的子树 一. 相同的树
点击查看题目 思路: bool isSameTree(… 大家好我是苏貝本篇博客带大家刷题如果你觉得我写的还不错的话可以给我一个赞吗感谢❤️ 目录 一. 相同的树二. 对称二叉树三. 另一棵树的子树 一. 相同的树
点击查看题目 思路: bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(pNULLqNULL)return true;//一个为空if(pNULL||qNULL)return false;//值不相同if(p-val!q-val)return false;//值相同比较左右子树return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}二. 对称二叉树
点击查看题目 思路: 这道题同相同的树相似只不过相同的树是比较2个树的同侧子树而这道题是比较不同侧子树
bool _isSymmetric(struct TreeNode* p,struct TreeNode* q){//p q都为空if(pNULLqNULL)return true;//p和q有一个为空if(pNULL||qNULL)return false;//p和q的值不同if(p-val!q-val)return false;//p和q的值相同再比较它们的不同侧子树return _isSymmetric(p-left,q-right)_isSymmetric(p-right,q-left);
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root-left,root-right);
}三. 另一棵树的子树
点击查看题目 思路: 注意右边例子中subRoot不是另一棵树的子树因为root多了一个节点 好了那本题的代码很轻易地就写出来了那这对不对呢
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(pNULLqNULL)return true;//一个为空if(pNULL||qNULL)return false;//值不相同if(p-val!q-val)return false;//值相同比较左右子树return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL)return false;if(root-valsubRoot-val)return isSameTree(root,subRoot);return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}很遗憾这是错的。为什么呢我们的本意是如果root-val subRoot-val但是root和subRoot不相同那么我们再比较root的左右子树和subRoot。基于这个想法我们再仔细看代码发现当root-valsubRoot-val时返回的是isSameTree(root,subRoot)的值那么如果返回false我们会直接跳过root的子树而返回root的双亲结点以下图的两个树为例 所以我们在root-valsubRoot-val时不能返回isSameTree(root,subRoot)的值而是当它的值为true时返回true否则再比较左右子树。代码如下
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(pNULLqNULL)return true;//一个为空if(pNULL||qNULL)return false;//值不相同if(p-val!q-val)return false;//值相同比较左右子树return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL)return false;if(root-valsubRoot-val){if(isSameTree(root,subRoot))return true;}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}也有一种简写的方法思路一样
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(pNULLqNULL)return true;//一个为空if(pNULL||qNULL)return false;//值不相同if(p-val!q-val)return false;//值相同比较左右子树return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL)return false;return isSameTree(root,subRoot)||isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}好了那么本篇博客就到此结束了如果你觉得本篇博客对你有些帮助可以给个大大的赞吗感谢看到这里我们下篇博客见❤️
