题目一: 单值二叉树
🚩⛲🌟⚡🥦💬
🚩题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
⛲题目描述:
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true
;否则返回 false
。
💬 示例:
示例1:
输入:[1,1,1,1,1,null,1] 输出:true
示例2:
输入:[2,2,2,5,2] 输出:false
🌟解题思路:
已知 A=B,B=C 可推出 A=C
- 若根节点的值与其子树结点相同,子树结点又与其子树结点相同,就可推出根节点与其子树的子 树相同,所以可以把这个大问题分为许多小问题: 父节点的值是否与其子节点的值相同
- 二叉树是由根节点和左子树、右子树构成,其每个子树又可以看作是由根节点和左右子树构成
- 利用递归思想,依次判断每个子树的根节点的值是否与其左右子树的值相同
- 空树不违背单值二叉树
⚡代码实现:
bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left&&root->left->val! = root->val)return false;if(root->right&&root->right->val! = root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}
题目二: 相同的树
🚩题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
⛲题目描述:
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
💬 示例:
示例1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例2:
输入:p = [1,2], q = [1,null,2] 输出:false
🌟解题思路:
- p 树的根节点和 q 树的根节点比较。
- p 树的左子树和 q 树的左子树比较。
- p 树的右子树和 q 树的右子树比较。
- 如果两个二叉树都为空,则两个二叉树相同。如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,若相同,再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
⚡代码实现:
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);
}