【Leetcode】单值二叉树、 相同的树、对称二叉树、另一颗树的子树、二叉树遍历、二叉树的前序遍历
创始人
2024-04-26 23:25:13
0

文章目录

  • OJ链接
  • 单值二叉树
  • 相同的树
  • 对称二叉树
  • 另一颗树的子树
  • 二叉树遍历
  • 二叉树的前序遍历

OJ链接

1、【单值二叉树】OJ链接
2、【相同的树】OJ链接
3、【对称二叉树】OJ链接
4、【另一棵树的子树】OJ链接
5、【二叉树遍历】OJ链接
6、【二叉树的前序遍历】OJ链接

单值二叉树

这里是引用> 思路:判断所有的节点是否都是相同的,采用递归的思想,用根和它的左右结点依次进行比较。> 在这里插入图片描述

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);
}

相同的树

这里是引用
思路:判断两个二叉树是否相同。 如果两个二叉树都为空,则两个二叉树相同。如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。如果两个二叉树都不为空,那么首先判断它们的根节点的值是否相同,若不相同则两个二叉树一定不同,若相同,再分别判断两个二叉树的左子树是否相同以及右子树是否相同,直至两树遍历结束。

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 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){return isSameTree(root->left,root->right);
}

另一颗树的子树

这里是引用
在这里插入图片描述
思路:检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树,遍历的到每个节点。将每个结点都当成subRoot的根节点来进行个比较,调用上面的问题相同的树来判断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);
}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);}

二叉树遍历

这里是引用
思路:用先序的方法先对字符串进行树的创建,创建好树用中序的方法进行遍历。
当数组碰到#时返回NULL。碰到字符依次遍历为树的节点。

#include 
#include
struct TreeNode
{char val;struct TreeNode*left;struct TreeNode* right;
};
//创建先序二叉树
struct TreeNode* rebuildTree(char *str,int * p)
{if(str[*p]=='#'){(*p)++;return NULL;}struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));if(root==NULL){perror("malloc");}root->val=str[(*p)++];root->left=rebuildTree(str,p);root->right=rebuildTree(str,p);return root;
}
//中序遍历
void Inorder(struct TreeNode*root)
{if(root==NULL){return ;}Inorder(root->left);printf("%c ",root->val);Inorder(root->right);
}
//销毁数据,释放空间
void TreeDestory(struct TreeNode*root)
{if(root==NULL){return ;}TreeDestory(root->left);TreeDestory(root->right);free(root);
}
int main() {char str[100];scanf("%s",str);int i=0;struct TreeNode* root=rebuildTree(str,&i);Inorder(root);TreeDestory(root);
}

二叉树的前序遍历

这里是引用
在这里插入图片描述
这与之前我们写的前序遍历有些不同,因为这道题要求我们将前序遍历里的结果返回,这也就需要我们创建数组来存放数据,相对之前遍历多出了创建数组开辟空间,计算所有节点所需的空间,防止开辟空间浪费。然后就是使用前序遍历依次将数据存放到数组当中。

int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root,int *a,int *i)
{if(root==NULL){return ;}a[(*i)++]=root->val;preorder(root->left,a,i);preorder(root->right,a,i);}
int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize=TreeSize(root);int *a=(int*)malloc(sizeof(int)*(*returnSize));int i=0;preorder(root,a,&i);return a;
}
最后:文章有什么不对的地方或者有什么更好的写法欢迎大家在评论区指出

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...