编号0023 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
首先我们要来判断下它们的根是否相等
根相等的话是否它们的左子树相等
是否它们的右子树相等
一直到子树为空为止
大家仔细思考下这个思路对不对
接下来我们开始敲代码
首先我们想极端一点的情况
如果这个俩空指针
说明这里肯定不用判断了 返回ture就行
如果说有一个空指针 一个不为空指针的话 那么肯定是不相同的返回假就可以
接下来如果值相等 我们能判断它们相同嘛 显然不可以
所以说我们这里直接上两个不同 返回假
之后我们再判断它的左子树右子树
整体代码如下
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); }
编号0024 对称二叉树
这里和前面相同的数的思路差不多
都是判断极值条件
之后递归展开 这里直接上代码 代码中会写明解题思路
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2) { //首先判断两个节点是否都为空 为空肯定相同 if(root1==NULL && root2==NULL) { return true; } // 如果一个节点为空 另外一个节点不为空 肯定不对称 if(root1==NULL || root2==NULL) { return false; } // 走到这里了肯定两个指针都不为空了 // 这里我们没法判断正确条件 只能判断错误条件 if(root1->val!=root2->val) { return false; } return _isSymmetric(root1->left,root2->right) && _isSymmetric(root1->right,root2->left); } bool isSymmetric(struct TreeNode* root) { // 这里首先判断节点是否为空 空肯定是对称的 if(root == NULL) { return true; } //之后这里要转换成左右子树的对称问题了 我们需要新建一个函数来写 return _isSymmetric(root->left,root->right); }
这里我们要注意的是 要转换成两个子树问题才可以做
而子树问题需要再创建一个递归函数 可能是这一题的难点之一
还有一个难点就是要观察结构
编号0025 另一个树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subtree-of-another-tree
我们这里只需要遍历一遍root 并且将root中的每一个节点和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); }
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
