🔥个人主页：胡萝卜3.0

🎬作者简介：C++研发方向学习者

📖个人专栏：  《C语言》《数据结构》 《C++干货分享》

⭐️人生格言：不试试怎么知道自己行不行

目录

一、二叉树选择题

题目1​

题目2

题目3

题目4

题目5

题目6

题目7

题目8

二、二叉树OJ题

2.1 单值二叉树

2.2 相同的树

2.3 对称二叉树

2.4 另一棵树的子树

2.5 二叉树的遍历

2.5.1 前序遍历

2.5.2 中序遍历

2.5.3 后序遍历

2.6 二叉树的构建及遍历

---

一、二叉树选择题

在看相关的选择题之前，我们先来学习一个二叉树的性质

根据二叉树的性质，完成以下选择题：

题目1

题目2

题目3

题目4

题目5

1.某完全二叉树按层次输出（同⼀层从左到右）的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为（）

A   ABDHECFG

B   ABCDEFGH

C   HDBEAFCG

D   HDEBFGCA

题目6

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则⼆叉树根结点为（）

A   E

B   F

C   G

D   H

根据先序遍历的结果，我们可以直接知道二叉树根节点为E

题目7

设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为____。

A   adbce   B   decab   C   debac   D   abcde

如果我们知道前序遍历+中序遍历  或者  中序遍历+后序遍历，就可以推导出二叉树的结构。

题目8

某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同⼀层从左到右）的序列为

A    FEDCBA    B   CBAFED     C   DEFCBA     D    ABCDEF

二、二叉树OJ题

2.1 单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

在看这到算法题之前，博主想到了一个问题：假设有三个数a,b,c，如果a==b,a==c，那可不可以说明a==b==c呢？答案：可以

ok，既然知道了这个问题，那接下来我么一起来看一下这道题。

思路：首先判断结点是否为空，如果结点为空，直接返回true；如果结点不为空，判断根节点和不为空的左右孩子中的值是否相等，如果相等，继续遍历左子树和右子树，如果不相等，直接返回false

将上面的思路转换成代码：

bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
    {
        return true;
    }
    //跟不为空的左右孩子进行比较
    if(root->left!=NULL&&root->val!=root->left->val)
    {
        return false;
    } 
    if(root->right!=NULL&&root->val!=root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

递归过程演示（每个结点视为一个函数桟帧）

2.2 相同的树

100. 相同的树 - 力扣（LeetCode）

所谓两棵相同的二叉树就是指结构相同，结点中的值相同

那如何判断结构是否相同呢？

如果两棵二叉树中对应的结点都为空，可以；如果两棵二叉树中对应的结点，一个为空，另一个不为空，结构就不相同

思路：首先判断两个根节点是否都为空，如果都为空，说明该结点结构相同，返回true，如果其中一个为空，另一个不为空，说明该结点结构不相同，返回false；如果结点都不为空，则判断结点中的值是否相等，若不相等，直接返回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);
}

递归过程演示（每个结点视为一个函数桟帧）

2.3 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

对称二叉树需要用到相同的树的思想，我们需要判断根节点的左子树和右子树是否是相同的树，如果是相同的树，则为对称二叉树；否则不是对称二叉树。

代码：

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

递归过程演示（每个结点视为一个函数桟帧）

2.4 另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

思路：运用到相同的树的思想，首先判断根节点是否为空，如果为空，直接返回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(isSameTree(root,subRoot))
    {
        return true;
    }
    //根节点不为空，并且根节点所在的树不和子树是相同的树，继续遍历左子树和右子树
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

递归过程演示（每个结点视为一个函数桟帧）

2.5 二叉树的遍历

2.5.1 前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

根据题目的意思以及返回值的类型，我们可以大致得出相应思路：
1、求出二叉树中结点个数

2、根据结点个数，向操作系统申请空间（此空间用于存放结点中的值）

3、前序遍历二叉树，将结点中的值放入申请的空间中

4、返回申请空间的地址

代码

//求二叉树的结点个数
 int BinaryTreeSize(struct TreeNode* root)
 {
    if(root==NULL)
    {
        return 0;
    }
    return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);
 }
//前序遍历
 void preOrder(struct TreeNode* root,int* arr,int* i)
 {
    if(root==NULL)
    {
        return;
    }
    arr[(*i)++]=root->val;
    preOrder(root->left,arr,i);
    preOrder(root->right,arr,i);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    //返回数组的大小
    *returnSize=BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    if(arr==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    int i=0;
    preOrder(root,arr,&i);
    return arr;
}

2.5.2 中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

根据题目的意思以及返回值的类型，我们可以大致得出相应思路：
1、求出二叉树中结点个数

2、根据结点个数，向操作系统申请空间（此空间用于存放结点中的值）

3、中序遍历二叉树，将结点中的值放入申请的空间中

4、返回申请空间的地址

代码

//求二叉树的结点个数
 int BinaryTreeSize(struct TreeNode* root)
 {
    if(root==NULL)
    {
        return 0;
    }
    return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);
 }
 //中序遍历，将结点中的值放入数组中
 void InOrder(struct TreeNode* root,int* arr,int* i)
 {
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left,arr,i);
    arr[(*i)++]=root->val;
    InOrder(root->right,arr,i);
 }
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    //求二叉树的结点个数
    *returnSize=BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    if(arr==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    int i=0;
    InOrder(root,arr,&i);
    return arr;
}

2.5.3 后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

根据题目的意思以及返回值的类型，我们可以大致得出相应思路：
1、求出二叉树中结点个数

2、根据结点个数，向操作系统申请空间（此空间用于存放结点中的值）

3、后序遍历二叉树，将结点中的值放入申请的空间中

4、返回申请空间的地址

代码

//求二叉树的结点个数
 int BinaryTreeSize(struct TreeNode* root)
 {
    if(root==NULL)
    {
        return 0;
    }
    return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);
 }
 //后序遍历
 void PostOrder(struct TreeNode* root,int* arr,int* i)
 {
    if(root==NULL)
    {
        return;
    }
    PostOrder(root->left,arr,i);
    PostOrder(root->right,arr,i);
    arr[(*i)++]=root->val;
 }
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=BinaryTreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    if(arr==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    int i=0;
    PostOrder(root,arr,&i);
    return arr;
}

2.6 二叉树的构建及遍历

二叉树遍历_牛客题霸_牛客网

我们之前说过，如果知道前序遍历+中序遍历  或者  中序遍历+后序遍历，就可以推导出二叉树的结构。但是现在题目中只给了我们前序遍历的结果，我们还能根据这个去构建二叉树的结构吗？

在这一题中是可以的，因为题中给我们的字符串是带有'#'的，这表示空指针，前序遍历的顺序是按照根节点->左子树->右子树，当我们遇到‘#’的时候，就无法继续往下遍历，而是要回到原来子树的根，这说的可能有点抽象，我们利用题目中给的测试样例来手动还原二叉树的结构：

代码

#include <stdio.h>
#include<stdlib.h>
//二叉树的链式结构
typedef struct BinaryTreeNode
{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
//为结点申请空间
BTNode* CreateNode(char x)
{
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    if(newnode==NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data=x;
    newnode->left=newnode->right=NULL;
    return newnode;
}
//根据先序遍历，创建二叉树
BTNode* CreateTree(char* arr,int* pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    //为从数组中遍历的数据开辟空间,成为根节点
    BTNode* root=CreateNode(arr[(*pi)++]);
    //创建左子树
    root->left=CreateTree(arr, pi);
    //创建右子树
    root->right=CreateTree(arr, pi);
    //返回根节点
    return root;
}
//中序遍历
void InOrder(BTNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main() {
    char arr[100];
    scanf("%s",arr);
    //根据先序遍历，创建二叉树
    int i=0;
    BTNode* root=CreateTree(arr,&i);
    //中序遍历
    InOrder(root);
    return 0;
}