【数据结构】树&&栈和队列题目解析＜leetcode&&牛客＞

用户10925563

发布于 2024-06-10 08:13:11

450

发布于 2024-06-10 08:13:11

文章被收录于专栏：c/c++&&linuxc/c++&&linux

主页：醋溜马桶圈-CSDN博客 专栏：数据结构_醋溜马桶圈的博客-CSDN博客 gitee：mnxcc (mnxcc) - Gitee.com

1.用队列实现栈（后进先出）

1.1 题目描述

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

1.2 题目分析

我们先把之前写的队列实现代码搬过来

用队列实现栈最主要的是实现栈后进先出的特点，而队列的特点是先进先出，那么我们可以用两个队列来实现

一个队列存数据
另一个队列在出数据的时候导数据

具体的接口有下面几个

1.2.1 初始化

我们先创建一个结构体来封装两个队列

初始化两个队列

1.2.2 销毁

我们要分析清楚这个结构，pst存q1,q2两个队列，需要先销毁q1和q2，然后释放pst

1.2.3 入栈

入栈我们入到不为空的队列中去，当q1不为空则入队列q1，否则入队列q2

1.2.4 出栈

出栈的时候就需要导数据了，比如数据都在q1中，q2为空，这时我们先判断空队列是哪一个，然后将非空队列前n-1个数据导入到空队列中，最后留一个数据就是栈顶数据，也是队列的队头数据，可以用QFront接口，先用top保存这个数据，接着pop掉这个数据，返回top

1.2.5 判空

1.2.6 返回栈顶元素

直接取不为空队列的队尾数据

1.3 代码示例

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//把队列的头尾封装在一个结构体中
 
//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);
 
//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

//初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
		//防止ptail成为野指针
	}
	pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

typedef struct MyStack{
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QInit(&(pst->q1));
	QInit(&(pst->q2));
	return pst;
}

void myStackPush(MyStack* obj, int x) {
	if (!QEmpty(&(obj->q1)))
	{
		QPush(&(obj->q1), x);
	}
	else
	{
		QPush(&(obj->q2), x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* empty = &(obj->q1);
	Queue* nonempty = &(obj->q2);
	if (!QEmpty(&(obj->q1)))
	{
		empty = &(obj->q2);
		nonempty = &(obj->q1);
	}
	while (QSize(nonempty) > 1)
	{
		QPush(empty, QFront(nonempty));
		QPop(nonempty);
	}
	int top = QFront(nonempty);
	QPop(nonempty);
	return top;

}

int myStackTop(MyStack* obj) {
	if (!QEmpty(&(obj->q1)))
	{
		return QBack(&(obj->q1));
	}
	else
	{
		return QBack(&(obj->q2));
	}
}

bool myStackEmpty(MyStack* obj) {
	return QEmpty(&(obj->q1)) && QEmpty(&(obj->q2));
}

void myStackFree(MyStack* obj) {
	QDestroy(&(obj->q1));
	QDestroy(&(obj->q2));
	free(obj);
}

2.用栈实现队列（先进先出）

2.1 题目描述

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

2.2 题目分析

我们先把之前写的数组栈的实现代码搬过来

用栈实现队列最主要的是实现队列先进先出的特点，而栈的特点是后进先出，那么我们可以用两个栈来实现：

一个pushst用来入队列
一个popst用来出队列

具体的接口有下面几个：

2.2.1 初始化

malloc一块空间来存两个栈，同时初始化这两个栈

2.2.2 入队列

入数据都入到pushst

2.2.3 出队列

出数据前先需要导数据：当popst为空且pushst不为空的时候，pushst的top数据依次push到popst中，然后返回pop的top数据，然后pop掉top数据；如果pop不为空，则直接返回poptop并pop

2.2.4 返回队头数据

2.2.5 判空

两个栈同时为空则为空

2.2.6 销毁

销毁还是依次销毁

2.3 代码示例

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//标识栈顶位置
	int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);

//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType * )realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst -> a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}
//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&(obj->pushst),x);
}

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    STPop(&(obj->popst));
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&(obj->popst)))
    {
        while(!STEmpty(&(obj->pushst)))
        {
            STPush(&(obj->popst),STTop(&(obj->pushst)));        
            STPop(&(obj->pushst));
        }
    }
    return STTop(&(obj->popst));
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->pushst));
    STDestroy(&(obj->popst));
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

3.循环队列

3.1 题目描述

题目链接：622. 设计循环队列 - 力扣（LeetCode）

3.2 题目分析

我们开辟空间的时候多开一个，k是队列的长度，我们开k+1个空间，定义一个front指向头，back的下一个指向尾

当front==back的时候，队列为空
当（back+1）%（k+）==front的时候，队列为满

这个多开的空间是移动的，出队列的时候front移动，入队列的时候back移动，当队列满的时候，（back+1）%（k+）一定==front

具体过程如下：

具体的接口有下面几个：

3.2.1 创建队列

用结构体封装一个数组，一个front和back，一个长度k来表示队列：

3.2.2 初始化

给队列开辟一块空间，给数组开辟k+1个空间，开始队列为空，front和back都为0

3.2.3 判空

front==back就为空

3.2.4 判满

当（back+1）%（k+）==front的时候，队列为满

3.2.5 插入

如果队列满了直接返回false，如果不为满则插入到back位置，然后back++到后一个位置指向尾的下一个

当back==k+1的时候，back回到数组第一个位置，即back=back%（k+1）

一个数模一个比他大的数不会改变这个值

3.2.6 删除

因为只有front到back之间的值是有效的，所以删除直接让front往后走就行

如果队列空了直接返回false，如果不为空则++front，返回true

同样，当front==k+1的时候，也需要回到数组第一个位置，即front=front%（k+1）

3.2.7 返回队头队尾的值

back指向队尾的下一个，所以返回队尾数据的时候返回的是k-1

如果back指向的是数组第一个，则返回数组的最后一个值，即a[k]

如果队列为空，则返回-1

3.2.8 销毁

3.2.9 队列的有效数据个数

现有一循环队列，其队头为front，队尾为rear(rear指向队尾数据的下一个位置)，循环队列长度为N,最多存储N-1个数据，其有效长度为(rear - front + N) % N

有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。

3.3 代码示例

typedef struct {
    int *a;
    int front;
    int back;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue* )malloc(sizeof(MyCircularQueue));
    obj->a=(int *)malloc(sizeof(int)*(k+1));
    obj->front=0;
    obj->back=0;
    obj->k=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->back]=value;
    obj->back++;
    obj->back%=(obj->k+1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    ++obj->front;
    obj->front%=(obj->k+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    if(obj->back==0)
        return obj->a[obj->k];
    else
        return obj->a[obj->back-1];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

4.对称二叉树

4.1 题目描述

题目链接：101. 对称二叉树 - 力扣（LeetCode）

4.2 题目分析

题目中说至少存在一个节点，所以我们只需要对比左右子树

写一个子函数对比左右子树：用递归的思路，左子树的左子树和右子树的右子树对比，左子树的右子树和右子树的左子树对比，我们只需要考虑几种情况：

如果左右子树都为空，则返回true
如果左右子树只有一棵为空，则返回false
如果左右子树都不为空，且值不相等，则返回false
如果左右子树都不为空，且值相等，则递归调用函数，对比左子树的左子树和右子树的右子树&&左子树的右子树和右子树的左子树，如果都为真则返回true

4.3 代码示例

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode*root1,struct TreeNode*root2)
{
    if(root1==NULL&&root2==NULL)
        return true;
    if(root1==NULL||root2==NULL)
        return false;
    if(root1->val!=root2->val)
        return false;
    return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left,root->right);
}

5.前序遍历

5.1 题目描述

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

5.2 题目分析

这道题的难点在于，前序遍历一遍之后需要将数值存在数组里，returnsize就是数组的大小

所以我们先构建一个函数来计算节点的个数

然后我们前序遍历，遍历的同时将数值存到数组里

最后再函数里先保存数组的大小，开辟一个数组，用i来控制数组往后走，为了防止局部变量出函数销毁，我们取i的地址

5.3 代码示例

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//int i=0;
void preorder(struct TreeNode*root,int *a,int *i)
{
    if(root==NULL)
        return;
    a[(*i)++]=root->val;
    preorder(root->left,a,i);
    preorder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    int *a=(int*)malloc(sizeof(int)*n);
    *returnSize=n;
    int i=0;
    preorder(root,a,&i);
    return a;
}

6.左叶子之和(C++)

6.1 题目描述

6.2 题目分析

我们以一个二叉树为例

左叶子的特点是什么？

是左节点并且没有左右孩子节点

所以我们用leftnode保存root->lefe节点，判断条件为leftnode存在，并且不存在leftnode->left和leftnode->right，如果满足条件，则将val加到全局变量x中去，x的初始值为0，然后递归root->right 如果不满足条件，就继续递归root->left和root->right

6.3 代码示例

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int count=0;
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr)
            return 0;
        TreeNode* leftnode=root->left;
        if(leftnode&&!leftnode->left&&!leftnode->right)
        {
            count +=leftnode->val;
            sumOfLeftLeaves(root->right);
        }
        else {
        {
            sumOfLeftLeaves(root->left);
            sumOfLeftLeaves(root->right);
        }
        }
        return count;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-09，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度