您现在的位置是：首页 > IT要闻

当前栏目

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

面试

2023-04-18 16:13:27 时间

二叉树

一、前言
二、学习刷题网站
三、刷题
三、小结

一、前言

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

二、学习刷题网站

在这里插入图片描述

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

三、刷题

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

三、小结

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

点击链接一起刷题吧

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程