=========================================================================
主页点击直达:个人主页
我的小仓库:代码仓库
C语言偷着笑:C语言专栏
数据结构挨打小记:初阶数据结构专栏
Linux被操作记:Linux专栏
LeetCode刷题掉发记:LeetCode刷题
算法头疼记:算法专栏
=========================================================================
目录
前言:
LeetCode 965.单值二叉树
LeetCode 100.相同的树
LeetCode 101.对称二叉树
LeetCode 144 145 94 .二叉树的前、中、后序遍历
LeetCode 572.另一棵树的子树
前言:
在之前的文章讲解了二叉树的链式结构的实现以及前、中、后序的遍历。不知道大家看完后有没有理解和有所收获,今天基于那篇文章给大家分享讲解几道经典的题目,更便于大家的理解和深入。
二叉树的题目一定要会两个思想:
第一个思想:拆分 一定要将二叉树拆分为根、左子树、右子树首先就是要判断根结点是否为空。第二个思想:递归,善于使用递归。
LeetCode 965.单值二叉树
OJ链接
题目描述:
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回
true
;否则返回false
。示例 1:
输入:[1,1,1,1,1,null,1] 输出:true示例 2:
输入:[2,2,2,5,2] 输出:false审题总结:
判断一个二叉树这所有节点的值是否相等,相等返回true,否则返回false;
思路讲解:首先判断根是否为空,如果为空直接返回true。不为空判断左子树是否存在,存在的话判断和根节点的值是否相等,如果相等返回true,否则返回false;继续判断右子树是否存在,存在的话判断和根节点的值是否相等,如果相等返回true,否则返回法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); }
LeetCode 100.相同的树
OJ链接
题目描述:给你两棵二叉树的根节点
p
和q
,编写一个函数来检验这两棵树是否相同如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true示例 2:
输入:p = [1,2], q = [1,null,2] 输出:false示例 3:
输入:p = [1,2,1], q = [1,1,2] 输出:false思路讲解:
先将根拆结点拆分出来,两个根节点有三种情况,都为空、两个根节点中有一个为空。如果都为空,则返回true;如果有一个为空则返回false。根节点判断完成后判断根节点的值是否相等;使用递归遍历左子树和右子树。
接口代码
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); }
LeetCode 101.对称二叉树
OJ链接
题目描述:
给你一个二叉树的根节点
root
, 检查它是否轴对称。示例 1:
输入:root = [1,2,2,3,4,4,3] 输出:true示例 2:
输入:root = [1,2,2,null,3,null,3] 输出:falses思路讲解:
这个题目和上个题目非常的相似,还是拆分为根、左子树、右子树。这里将两个子树看成单独的树,就和上面题的思路大差不差了。不同的是要判断左边的值和右边的值是否相等,这样才算对称。
实现代码文章来源:https://www.toymoban.com/news/detail-714693.html
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->right) &&isSameTree(p->right,q->left); } bool isSymmetric(struct TreeNode* root){ if(root!=NULL) { return isSameTree(root->left,root->right); } else return true; }
LeetCode 144 145 94 .二叉树的前、中、后序遍历
前序遍历OJ链接
中序遍历OJ链接
后序遍历OJ链接
关于二叉树的前、中、后序遍历的文章点击直达,这里我不做介绍。由于这三个题目是差不多只是将遍历的值用数组的形式便是出来,所以我就只讲解前序遍历、中、后序遍历交给大家练习。
题目描述:给你一棵二叉树的根节点
root
,返回其节点值的 后序遍历 。示例 1:
输入:root = [1,null,2,3] 输出:[3,2,1]示例 2:
输入:root = [] 输出:[]示例 3:
输入:root = [1] 输出:[1]思路讲解:
首先求出这棵二叉树有几个结点,根据结点动态开辟相应大小的空间。将根节点、动态开辟的数组,变量的地址,交给一个前序遍历的函数,根据前序遍历的规则,进行递归给数组赋值。
实现代码
int treesize(struct TreeNode*root) { return root==NULL? 0:treesize(root->left)+treesize(root->right)+1; } void preoder(struct TreeNode *root,int *a,int *pi) { if(root==NULL) return; a[(*pi)++]=root->val; preoder(root->left,a,pi); preoder(root->right,a,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize){ int n=treesize(root); int *a=(int *)malloc(sizeof(int )*n); int j=0; preoder(root,a,&j); *returnSize=n; return a; }
LeetCode 572.另一棵树的子树
OJ链接
题目描述:
给你两棵二叉树
root
和subRoot
。检验root
中是否包含和subRoot
具有相同结构和节点值的子树。如果存在,返回true
;否则,返回false
。二叉树tree
的一棵子树包括tree
的某个节点和这个节点的所有后代节点。tree
也可以看做它自身的一棵子树。示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2] 输出:true示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出:falses思路讲解:
这个题和上面的LeetCode 100.相同的树基本上也大差不差。首先判断根节点是否为空,如果根节点为空,则直接返回false;不为空则直接使用是否为相同的树判断函数,判断所给树是否为子树,如果为真则直接返回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); }
今天的分享就到此结束了,希望大家阅读完可以有所收获,同时也感谢各位看官的三连支持。文章有问题可以直接留言,我一定及时认真的修改。文章来源地址https://www.toymoban.com/news/detail-714693.html
到了这里,关于【LeetCode】——链式二叉树经典OJ题详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!