一、前言
二叉树是数据结构中重要的一个章节，他的重要性也不言而喻，在未来不管是笔试还是面试都会遇到这类的题目，所以接下来我就会把一些常考的题目全部整理出来供大家学习指正。
二、学习刷题网站
点击下面链接即可进行刷题学习
开始刷题
三、刷题
先说明一下一些题目取自牛客网面试必刷TOP101
里面的一些题目在我以前的文章详细写到过，如果没有用新的方法就不会再做讲解
LeetCode刷题 —— 手撕二叉树
<1>重建二叉树
题目链接
描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：n ≤ 2000，节点的值 −10000 ≤ val ≤ 10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
示例2
输入：[1],[1]
返回值：{1}
示例3
输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}
思路分析：
递归
前序遍历可以确定根节点，中序遍历可以确定左右子树。
通过观察，先序的第一个数字就是根节点，然后在中序找到相等的节点(每个节点数字不同)，用中序划分左右子树，在前序相同的位置前序也被划分为左右子树，而前序的左右子树第一个节点为他们的根节点。
通过这个规律就可以用递归解决问题：
左右子树各创建两个数组（前序和中序）,并且计算出大小，递归到下一层，如此循环。
要注意的是： 在放左子树前序的时候是从第二个位置开始的（第一个元素为根）。
struct TreeNode* BuyNode(int x)
{
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
root->val = x;
root->left = NULL;
root->right = NULL;
return root;
}
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
//判空
if(vinLen == 0)
{
return NULL;
}
//第一个节点为根
struct TreeNode* head = BuyNode(pre[0]);
//通过中序遍历找根
int root = 0;
for(int i = 0; i < vinLen; i++)
{
if(pre[0] == vin[i])
{
root = i;
break;
}
}
//左子树
int size_left = root;
int* pre_left = (int*)malloc(sizeof(int) * size_left);
int* vin_left = (int*)malloc(sizeof(int) * size_left);
for(int i = 0; i < size_left; i++)
{
pre_left[i] = pre[i + 1];//第一个元素为根
vin_left[i] = vin[i];
}
//右子树
int size_right = vinLen - root - 1;
int* pre_right = (int*)malloc(sizeof(int) * size_right);
int* vin_right = (int*)malloc(sizeof(int) * size_right);
int j = 0;//数组从0下标开始
for(int i = root + 1; i < vinLen; i++)
{
pre_right[j] = pre[i];
vin_right[j] = vin[i];
j++;
}
head->left = reConstructBinaryTree(pre_left, size_left, vin_left, size_left);
head->right = reConstructBinaryTree(pre_right, size_right, vin_right, size_right);
return head;
}
<2>输出二叉树的右视图
描述
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
数据范围：0 ≤ n ≤ 10000
要求： 空间复杂度O(n)，时间复杂度O(n)
如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
所以对应的输出为[1,3,5]。
示例1
输入：[1,2,4,5,3],[4,2,5,1,3]
返回值：[1,3,5]
备注：
二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。
思路分析：
重建二叉树 + 层序遍历
第一步是重建二叉树，跟上一题一样，重建二叉树完成了以后就是把每一层的最后一个节点找到。这里就可以用层序遍历，而怎么知道每一层的最后一个元素是什么呢？
层序遍历用的是队列，我们计算队列的大小就知道每一层有多少个节点，然后每pop一个节点就size--，当size减到0时就是一层的最后一个元素。
typedef struct TreeNode* QDateType;
typedef struct QueueNode
{
struct QueueNode* next;
QDateType date;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
bool QueueEmpty(Queue* pst);
void QueueInit(Queue* pst)
{
pst->head = pst->tail = NULL;
}
void QueueDestroy(Queue* pst)
{
QueueNode* cur = pst->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pst->head = pst->tail = NULL;
}
void QueuePush(Queue* pst, QDateType x)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
if (pst->head == NULL)
{
pst->head = newnode;
pst->tail = newnode;
}
else
{
pst->tail->next = newnode;
pst->tail = newnode;
}
}
void QueuePop(Queue* pst)
{
if (pst->head->next == NULL)
{
free(pst->head);
pst->head = pst->tail = NULL;
}
else
{
QueueNode* next = pst->head->next;
free(pst->head);
pst->head = next;
}
}
QDateType QueueBack(Queue* pst)
{
return pst->tail->date;
}
QDateType QueueFront(Queue* pst)
{
return pst->head->date;
}
//真返回非0
bool QueueEmpty(Queue* pst)
{
return pst->head == NULL;
}
int QueueSize(Queue* pst)
{
QueueNode* cur = pst->head;
int size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
struct TreeNode* BuyNode(int x)
{
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
root->val = x;
root->left = NULL;
root->right = NULL;
return root;
}
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen ) {
//判空
if(vinLen == 0)
{
return NULL;
}
//第一个节点为根
struct TreeNode* head = BuyNode(pre[0]);
//通过中序遍历找根
int root = 0;
for(int i = 0; i < vinLen; i++)
{
if(pre[0] == vin[i])
{
root = i;
break;
}
}
//左子树
int size_left = root;
int* pre_left = (int*)malloc(sizeof(int) * size_left);
int* vin_left = (int*)malloc(sizeof(int) * size_left);
for(int i = 0; i < size_left; i++)
{
pre_left[i] = pre[i + 1];//第一个元素为根
vin_left[i] = vin[i];
}
//右子树
int size_right = vinLen - root - 1;
int* pre_right = (int*)malloc(sizeof(int) * size_right);
int* vin_right = (int*)malloc(sizeof(int) * size_right);
int j = 0;//数组从0下标开始
for(int i = root + 1; i < vinLen; i++)
{
pre_right[j] = pre[i];
vin_right[j] = vin[i];
j++;
}
head->left = reConstructBinaryTree(pre_left, size_left, vin_left, size_left);
head->right = reConstructBinaryTree(pre_right, size_right, vin_right, size_right);
return head;
}
int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
struct TreeNode* root = reConstructBinaryTree(xianxu, xianxuLen, zhongxu, zhongxuLen);
Queue q;
QueuePush(&q, root);
//记录返回数组
int* tmp = (int*)malloc(sizeof(int) * 10000);
int i = 0;
while(!QueueEmpty(&q))
{
int size = QueueSize(&q);
while(size--)
{
struct TreeNode* ret = QueueFront(&q);
QueuePop(&q);
if(size == 0)
{
tmp[i++] = ret->val;
}
//入左子树
if(ret->left)
{
QueuePush(&q, ret->left);
}
//入右子树
if(ret->right)
{
QueuePush(&q, ret->right);
}
}
}
*returnSize = i;
return tmp;
}
三、小结
我们可以看到二叉树基本解题思路就是递归，如果递归想不出代码，可以直接看最后一步怎么实现，其次一定要多画图理解。
点击链接一起刷题吧