1.LeetCode965 单值二叉树
解题思路:
遍历二叉树,并且每一个节点值都和根节点的值进行比对,如果不等于根节点的值,则不是单值树。
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);
}
2.LeetCode100 相同的树
解题思路:
首先比较根节点是否相同,然后分别比较左右子树是否相同。
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);
}
3.LeetCode101 对称二叉树
解题思路:
判断一个树是否对称,首先要判断左右孩子是否对称相等,还需要判断左孩子的左子树是否和右孩子的右子树对称,左孩子的右子树是否和右孩子的左子树对称。
bool cmp(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 cmp(p->left,q->right)&&cmp(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){
if(root==NULL)return true;
return cmp(root->left,root->right);
}
4.LeetCode572 另一棵树的子树
解题思路:
判断t是否为s的子树,需要判断t是否和s的某一个子树相同,所以此题就是判断两棵树是有相同的逻辑。
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(issametree(root,subRoot))return true;
//与左树相同或与右树相同
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
5.牛客KY11 二叉树遍历
解题思路:
在先序遍历的过程中构建每一个节点,然后按中序遍历打印,先序遍历与中序遍历在上一篇博客中以详细讲解,本文不再赘述文章来源:https://www.toymoban.com/news/detail-416667.html
#include <stdio.h>
//树的节点
struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
char val;
}node;
//先序遍历构建二叉树
struct TreeNode* createTree(char* a,int* pi)
{
if(a[*pi]=='#')
{
(*pi)++;
return NULL;
}
struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
//根节点的值
root->val=a[(*pi)++];
//左孩子
root->left=createTree(a, pi);
//右孩子
root->right=createTree(a, pi);
return root;
}
//中序遍历
void inorder(struct TreeNode* root)
{
if(root==NULL)return ;
inorder(root->left);
printf("%c ",root->val);
inorder(root->right);
}
int main() {
char a[100];
scanf("%s",a);
int i=0;
struct TreeNode* root=createTree(a,&i);
inorder(root);
return 0;
}
本文到此结束,码文不易,还请多多支持哦!文章来源地址https://www.toymoban.com/news/detail-416667.html
到了这里,关于二叉树基础oj题自测的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!