前言
二叉树 主要就是玩递归,相信大家学完 二叉树 以后,对递归有了更加深层的理解,可以试着做几道oj题,练一下手.
一、单值二叉树
声明:
题目来源于–力扣
题目链接: 传送门
题目描述:
如果 二叉树 每个节点都具有相同的值，那么该 二叉树 就是 单值二叉树 。
给定一棵树,如果这棵树是 单值二叉树 时，
返回 true；
否则返回 false。
示例1:
输入：[1,1,1,1,1,null,1] 输出：true
示例2:
输入：[2,2,2,5,2] 输出：false
解题思路:
- 递归结束条件,遇到NULL返回true
- 判断根节点的值与左子树的值是否相等.
不相等返回false - 判断根节点的值与右子树的值是否相等.
不相等返回false - 返回递归遍历这颗树的逻辑值.
代码实现:
bool isUnivalTree(struct TreeNode* root){ if(root==NULL) { return true; } //判断根节点的值与左子树的值是否相等. if(root->left&&root->val!=root->left->val) { return false; } //判断根节点的值与右子树的值是否相等. if(root->right&&root->val!=root->right->val) { return false; } return isUnivalTree(root->left)&&isUnivalTree(root->right); }
提交记录:
二、相同的树
声明:
题目来源于–力扣
题目链接: 传送门
题目介绍:
给你两棵 二叉树 的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
相同返回:true
不同返回:false
示例1:
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例2:
输入：p = [1,2], q = [1,null,2] 输出：false
解题思路
1.先考虑两棵树其中一棵为NULl的情况,返回false
(注意不是指一整颗树为NULl,而是指一方节点).
例如:
示例2中,第一颗树的左子树是值为2的结点,但是第二棵树的左子树是NULL.
2.两棵树都为NULL,返回true
3.判断两颗树的结点值是否相等.
不相等则返回false
4.返回最后遍历结果的逻辑值.
代码实现:
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); }
提交记录:
三、对称二叉树
声明:
题目来源于–力扣
题目链接:
题目介绍:
给你一个 二叉树 的根节点 root ， 检查它是否轴对称。
对称:返回true.
不对称:返回false
输入：root = [1,2,2,3,4,4,3] 输出：true
输入：root = [1,2,2,null,3,null,3] 输出：false
解题思路:
难点在于,对称 二叉树 是需要遍历到左子树之后,回到根节点,去与右子树比较,为了实现这一要求,我们可以另写一个函数,直接将这棵树用两个root访问.从最开始的根节点开始,将这颗 二叉树 切割为 二叉树 .
1.创建一个子函数check.参数为(struct TreeNode* root1,struct TreeNode* root2)
2.先判断这两颗树的根节点是否为NULL.为空则直接返回true.
3.一方为NULl时:返回false.
4.判断root1的值和root2的值是否相等.
5.root1递归时先访问其左子树,root2递归时先访问其右子树.
6.root1递归 后访问右子树,root2递归 后访问左子树.
7.返回递归结果的逻辑值.
代码实现
bool check(struct TreeNode* root1,struct TreeNode* root2) { if(root1==NULL&&root2==NULL) return true; //上面已经判断了都为NULL时的情况,则此时判断如果一方为空 if(root1==NULL||root2==NULL) return false; if(root1->val!=root2->val) return false; //注意这里的递归顺序,重点 return check(root1->left,root2->right)&& check(root1->right,root2->left); } bool isSymmetric(struct TreeNode* root){ return check(root,root); }
提交记录:
练习完这几道oj题,相信大家对二叉树有了更深层的理解了.
如果文章有帮助的话,可以给牛牛来一个一键三连吗?
