• 【牛客网面试必刷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}

    思路分析：

    递归

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186

    三、小结

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

    点击链接一起刷题吧

  • 相关阅读:
    计算机网络——网络层（多协议标签交换MPLS、软件定义网络SDN）
    c++源码编译过程(翻译阶段)的若干细节概要
    ensp中查看带宽信息
    抖音、快手、视频号排兵布阵VR直播
    【图像分割】基于差分进化算法优化模糊熵实现多级图像阈值分割附matlab代码
    XTU OJ 1170 学习笔记
    GnosisSafe.sol 学习 （一）
    Ubuntu 20.04 安装 mysql 8
    Redis实战之共享session + jwt 实现登录拦截、刷新token
    罗丹明RB/四甲基罗丹明标记水杨苷Salicin, Rhodamine B/TRITC labeled；Rhodamine B/TRITC-Salicin
  • 原文地址：https://blog.csdn.net/qq_66314292/article/details/126633200