【牛客网面试必刷TOP101】二叉树篇（三）

二叉树

一、前言

二叉树是数据结构中重要的一个章节，他的重要性也不言而喻，在未来不管是笔试还是面试都会遇到这类的题目，所以接下来我就会把一些常考的题目全部整理出来供大家学习指正。

二、学习刷题网站

点击下面链接即可进行刷题学习
开始刷题

三、刷题

先说明一下一些题目取自牛客网面试必刷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}

思路分析：

递归

前序遍历可以确定根节点，中序遍历可以确定左右子树。

通过观察，先序的第一个数字就是根节点，然后在中序找到相等的节点(每个节点数字不同)，用中序划分左右子树，在前序相同的位置前序也被划分为左右子树，而前序的左右子树第一个节点为他们的根节点。
通过这个规律就可以用递归解决问题：
左右子树各创建两个数组（前序和中序）,并且计算出大小，递归到下一层，如此循环。
要注意的是： 在放左子树前序的时候是从第二个位置开始的（第一个元素为根）。

structTreeNode*BuyNode(int x){structTreeNode* root =(structTreeNode*)malloc(sizeof(structTreeNode*));
    root->val = x;
    root->left =NULL;
    root->right =NULL;return root;}structTreeNode*reConstructBinaryTree(int* pre,int preLen,int* vin,int vinLen ){//判空if(vinLen ==0){returnNULL;}//第一个节点为根structTreeNode* 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时就是一层的最后一个元素。

typedefstructTreeNode* QDateType;typedefstructQueueNode{structQueueNode* next;
    QDateType date;}QueueNode;typedefstructQueue{
    QueueNode* head;
    QueueNode* tail;}Queue;

bool QueueEmpty(Queue* pst);voidQueueInit(Queue* pst){
    pst->head = pst->tail =NULL;}voidQueueDestroy(Queue* pst){
    QueueNode* cur = pst->head;while(cur){
        QueueNode* next = cur->next;free(cur);
        cur = next;}
    pst->head = pst->tail =NULL;}voidQueuePush(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;}}voidQueuePop(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;}intQueueSize(Queue* pst){
    QueueNode* cur = pst->head;int size =0;while(cur){
        size++;
        cur = cur->next;}return size;}structTreeNode*BuyNode(int x){structTreeNode* root =(structTreeNode*)malloc(sizeof(structTreeNode*));
    root->val = x;
    root->left =NULL;
    root->right =NULL;return root;}structTreeNode*reConstructBinaryTree(int* pre,int preLen,int* vin,int vinLen ){//判空if(vinLen ==0){returnNULL;}//第一个节点为根structTreeNode* 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 ){structTreeNode* 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--){structTreeNode* 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;}

三、小结

我们可以看到二叉树基本解题思路就是递归，如果递归想不出代码，可以直接看最后一步怎么实现，其次一定要多画图理解。

点击链接一起刷题吧