当前位置：首页 > news >正文

【leetcode】相同的树➕对称二叉树➕另一棵树的子树

news 2025/9/12 19:50:27

大家好，我是苏貝，本篇博客带大家刷题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

一. 相同的树

点击查看题目

在这里插入图片描述

思路:

在这里插入图片描述

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(p==NULL&&q==NULL)return true;//一个为空if(p==NULL||q==NULL)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(p==NULL&&q==NULL)return true;//p和q有一个为空if(p==NULL||q==NULL)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(p==NULL&&q==NULL)return true;//一个为空if(p==NULL||q==NULL)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(root==NULL)return false;if(root->val==subRoot->val)return isSameTree(root,subRoot);return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

在这里插入图片描述
很遗憾，这是错的。为什么呢？我们的本意是：如果root->val == subRoot->val，但是root和subRoot不相同，那么我们再比较root的左右子树和subRoot。基于这个想法，我们再仔细看代码，发现当root->val==subRoot->val时，返回的是isSameTree(root,subRoot)的值，那么如果返回false，我们会直接跳过root的子树而返回root的双亲结点（以下图的两个树为例）

在这里插入图片描述

所以我们在root->val==subRoot->val时不能返回isSameTree(root,subRoot)的值，而是当它的值为true时返回true，否则再比较左右子树。代码如下：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//都为空if(p==NULL&&q==NULL)return true;//一个为空if(p==NULL||q==NULL)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(root==NULL)return false;if(root->val==subRoot->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(p==NULL&&q==NULL)return true;//一个为空if(p==NULL||q==NULL)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(root==NULL)return false;return isSameTree(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}