【二叉树】OJ题目
🌟个人主页：落叶
目录
单值⼆叉树
【单值二叉树】代码
相同的树
【相同二叉树】代码
对称⼆叉树
【对称二叉树】代码
另一颗树的子树
【另一颗树的子树】代码
二叉树的前序遍历
【二叉树前序遍历】代码
二叉树的中序遍历
【二叉树中序遍历】代码
二叉树的后序遍历
【二叉树的后序遍历】代码
⼆叉树的构建及遍历
【⼆叉树的构建及遍历】代码
单值⼆叉树
单值⼆叉树就是每个节点的数值都是一样的
链接：单值二叉树
思路：把当前节点的左子树的数值，和当前节点数值进行比较，不一样的话就不是单值⼆叉树，返回false。
右子树也是一样的，把当前节点的右子树的数值，和当前节点数值进行比较，不一样的话就不是单值⼆叉树，返回false。
判断，当递归到空的时候返回true
判断左子树节点是不是空&&判断，左子树的数值和当前节点的数值，不等于返回false。
再判断右子树节点是不是空&&判断，右子树的数值和当前节点的数值，不等于返回false。
递归下去，左右子树都和当前节点进行比较，不一样返回false。
【单值二叉树】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/typedef struct TreeNode BT;
bool isUnivalTree(struct TreeNode* root) {//是空直接返回trueif(root == NULL){return true;}//判断左子树和当前节点的值，不一样就不是单值⼆叉树返回falseif(root->left != NULL && root->left->val != root->val){return false;}//判断右子树和当前节点的值，不一样就不是单值⼆叉树返回falseif(root->right != NULL && root->right->val != root->val){return false;}//递归下去，判断是不是truereturn isUnivalTree(root->left) && isUnivalTree(root->right);}相同的树
两个一模一样的二叉树
链接：相同的树
思路：判断有一个节点为NULL或数值不一样，返回false。递归左子树和右子树。
判断当两边节点为空，返回true。
判断只有一个节点为空的话，不是相同二叉树吗，返回false。
判断数值，不一样的话不是相同二叉树，返回false。
递归两边的左子数 && 右子树
【相同二叉树】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/typedef struct TreeNode BT;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//判断节点为空，返回trueif(p==NULL && q==NULL){return true;}//只有一个节点为空，，不是相同二叉树，返回falseif(p==NULL|| q==NULL){return false;}//比较数值,不一样就不是相同二叉树，返回falseif(p->val != q->val){return false;}//递归，下去判断p和q的左子树和右子树return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}对称⼆叉树
链接：对称二叉树
思路：我们可以用【相同的树】思路，把根节点的左子树和右子树进行比较。
左边2节点的左子树和右边2节点的右子树进行比较，
传根节点的左子树和右子树。
递归的时候，左边左子树，和右的右子树比较，
左边的右子树，和右边的左子树比较。
【对称二叉树】代码
另一颗树的子树
root 和 subRoot是同一颗树调用相同的树，直接返回。
不一样的话，root 的子树和subRoot进行比较。
链接：对称二叉树
思路：先判断root节点为空的话返回false,然后再判断ROOT节点和subRoot是不是相同，相同返回true,递归左子树找相同的树，再找右子树。
判断root节点为空返回false。
调用相同的树函数，判断root节点下面是不是和subRoot一样，一样返回true。
递归root的左子树判断是不是和subRoot相同，再递归右子树。
【另一颗树的子树】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
//找相同树
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//判断节点为空，返回trueif(p==NULL && q==NULL){return true;}//只有一个节点为空，，不是相同二叉树，返回falseif(p==NULL|| q==NULL){return false;}//比较数值,不一样就不是相同二叉树，返回falseif(p->val != q->val){return false;}//递归，下去判断p和q的左子树和右子树return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){//root节点为空返回falseif(root == NULL){return false;}//判断root节点下面的节点，和subRoot是不是相同，相同返回trueif(isSameTree(root,subRoot)){return true;}//递归，遇到相同的另一颗子树返回true，两边都遇到NULL了就说明不相同return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
二叉树的前序遍历
链接：二叉树前序遍历
思路：求出二叉树节点个数，然后申请arr数组空间，空间大小为二叉树节点个数，然后前序遍历，递归遇到NULL就返回，不是NULL往数组存放数值，然后继续往下递归。
第一步：求出二叉树的节点个数，根+左子树节点个数+右子树节点个数。
第二步：动态申请，arr数组空间，空间大小是二叉树节点个数。
第三步：前序遍历，如果左子树为NULL，那么左子树一个节点都没有了，不为NULL，把节点数值存放到arr数组，然后递归。
最后返回arr数组。
【二叉树前序遍历】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode TreeNode;
//求出二叉树节点个数
int size(TreeNode* root)
{if(root == NULL){return 0;}//二叉树个数是:根+左子数节点个数+右子数节点个数return 1 + size(root->left) + size(root->right);
}
//前序遍历
void bian(TreeNode* root,int* arr,int *i)
{if(root==NULL){return;}//根-左-右arr[(*i)++] = root->val;bian(root->left,arr,i);bian(root->right,arr,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {//求出二叉树节点个数*returnSize = size(root);//动态申请--arr数组空间大小int* arr = (int*)malloc(sizeof(int)*(*returnSize));int i=0;//前序遍历bian(root,arr,&i);//返回return arr;
}二叉树的中序遍历
链接：二叉树的中序遍历
第一步：求出二叉树的节点个数，根+左子树节点个数+右子树节点个数。
第二步：动态申请，arr数组空间，空间大小是二叉树节点个数。
第三步：中序遍历，如果左子树为NULL，那么左子树一个节点都没有了，不为NULL，把节点数值存放到arr数组，然后递归。
最后返回arr数组。
【二叉树中序遍历】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
typedef struct TreeNode SL;
//求出二叉树节点个数
int size(SL* root)
{if(root == NULL){return 0;}//二叉树个数是:根+左子数节点个数+右子数节点个数return 1 + size(root->left) + size(root->right);
}
//中序遍历
void zho(SL* root ,int* arr,int* i)
{if(root == NULL){return ;}//中序遍历:左-根-右zho(root->left,arr,i);arr[(*i)++] = root->val;zho(root->right,arr,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {//求出二叉树节点个数*returnSize = size(root);//动态申请--arr数组空间大小int* arr = (int*)malloc(sizeof(int) * (*returnSize));//中序遍历int i = 0;zho(root,arr,&i);//返回return arr;
}二叉树的后序遍历
链接：二叉树的后序遍历
第一步：求出二叉树的节点个数，根+左子树节点个数+右子树节点个数。
第二步：动态申请，arr数组空间，空间大小是二叉树节点个数。
第三步：中序遍历，如果左子树为NULL，那么左子树一个节点都没有了，不为NULL，把节点数值存放到arr数组，然后递归。
最后返回arr数组。
【二叉树的后序遍历】代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode SL;//求出二叉树节点个数
int size(SL* root)
{if(root== NULL){return 0;}//二叉树个数是:根+左子数节点个数+右子数节点个数return 1 + size(root->left) + size(root->right);
}
//后序遍历
void ho(SL*root,int*arr,int* i)
{if(root==NULL){return;}//后序遍历= 左-右-根ho(root->left,arr,i);ho(root->right,arr,i);arr[(*i)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {//求出二叉树节点个数*returnSize = size(root);//动态申请--arr数组空间大小int* arr = (int*)malloc(sizeof(int) * (*returnSize));//后序遍历int i = 0;ho(root,arr,&i);//返回arrreturn arr;
}⼆叉树的构建及遍历
链接：⼆叉树的构建及遍历
思路：需要输入长度不超过100的字符，然后再通过（前序遍历）二叉树，然后输出二叉树中序遍历结果。
创建二叉树节点结构体，输入长度不超过100的字符串。
第一步：根据字符串（前序遍历）创建二叉树，传数组，和下标过去，
if判断如果arr数组下标为*i 的 字符 == # ，返回NULL，i++往后走。
创建二叉树节点给ROOT，传arr数组下标为*i 的 字符 ，申请空间，把传过来的值给tab->arr,
再把tab的左子树和右子树置为NULL。
（*i）++往后走，递归创建左子树，递归创建右子树，返回ROOT节点 ，最后一次返回的就是根节点了。
创建完二叉树，返回根节点后，进行输出，二叉树中序遍历结果，传二叉树根节点，
进行中序遍历（左-根-右）。
【⼆叉树的构建及遍历】代码
#include <stdio.h>
#include <unistd.h>
//二叉树节点结构体
typedef struct kko
{char arr;//存放字符struct kko* zuo;//左子树struct kko* you;//右子树
}SL;//创建二叉树节点
SL* cj_jied(char x)
{//申请节点空间SL* tab = (SL*)malloc(sizeof(SL));tab->arr = x;tab->you = tab->zuo = NULL;return tab;}//前序遍历
SL* qian(char* arr,int* i)
{if(arr[*i] == '#'){(*i)++;return NULL;}//创建二叉树节点给ROOTSL* root = cj_jied(arr[*i]);(*i)++;root->zuo = qian(arr , i);//递归创建左子树root->you = qian(arr ,i);//递归创建右子树return root;
}
//中序遍历
void zho(SL* root)
{if(root == NULL){return;}//中序遍历——根——左——右zho(root->zuo);//递归遍历左子树printf("%c ",root->arr);zho(root->you);//递归遍历右子树
}int main() {char add[100];scanf("%s", add);//根据字符串（前序遍历）创建二叉树int i = 0;SL* root = qian(add,&i);//输出二叉树中序遍历结果zho(root);return 0;
}