【代码随想录】4

栈篇

删除字符串中所有相邻重复项

typedef struct Stack//定义一个栈的结构体变量	
{
	char * a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);//断言，防止为空指针
	ps->a = NULL;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容，
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0，就先给4个空间大小，后面如果满的话，容量扩大1倍
		 char* newnode = (char*)realloc(ps->a,sizeof(char)* newcapcity);//申请空间，将申请好的空间首地址传给newnode指针
		 assert(newnode);//断言，防止malloc失败
		 ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top ==0;//ps->top为栈中元素个数.==0栈中无元素，无元素要返回1， 无元素ps->t0p==0，这个表达式结果是1，返回1;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈内无元素，继续出栈
	ps->top--;
}
// 获取栈顶元素
char StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数，由于数组下标是从0开始，所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = NULL;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}




char* removeDuplicates(char* s) {
Stack st;
StackInit(&st);

    while (*s) {
        if (StackEmpty(&st) || StackTop(&st) != *s) {  // 修改了条件检查
            StackPush(&st, *s);
        } else {
            if(!StackEmpty(&st) && StackTop(&st) == *s) {  // 检查栈顶是否和当前字符相同
                StackPop(&st);  // 如果相同，弹出栈顶元素
            }
        }
        s++;
    }
    





int num=StackSize(&st);
int j=num-1;
char*a=(char*)malloc(sizeof(char)*(num+1));
if(a==NULL)
perror("malloc fail");
while(!StackEmpty(&st))
{
a[j]=StackTop(&st);
StackPop(&st);
j--;

}
a[num]='\0';
return a;
StackDestroy(&st);
free(a);
}

逆波兰表达式求值

typedef struct Stack//定义一个栈的结构体变量	
{
	int * a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);//断言，防止为空指针
	ps->a = NULL;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容，
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0，就先给4个空间大小，后面如果满的话，容量扩大1倍
		 int* newnode = (int*)realloc(ps->a,sizeof(int)* newcapcity);//申请空间，将申请好的空间首地址传给newnode指针
		 assert(newnode);//断言，防止malloc失败
		 ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top ==0;//ps->top为栈中元素个数.==0栈中无元素，无元素要返回1， 无元素ps->t0p==0，这个表达式结果是1，返回1;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈内无元素，继续出栈
	ps->top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数，由于数组下标是从0开始，所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = NULL;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}

int evalRPN(char** tokens, int tokensSize) {
Stack st;
StackInit(&st);

for(int i=0;i<tokensSize;i++)
{char*token=tokens[i];
if(strcmp(tokens[i],"+")==0||strcmp(tokens[i],"-")==0||strcmp(tokens[i],"*")==0||strcmp(tokens[i],"/")==0)
  { int num1= StackTop(&st);
    StackPop(&st);
    int num2=StackTop(&st);
    StackPop(&st);
     if (strcmp(tokens[i],"+")==0)StackPush(&st,num2+num1);
      if (strcmp(tokens[i],"-")==0)StackPush(&st,num2-num1);
      if (strcmp(tokens[i],"*")==0)StackPush(&st,num2*num1);
      if (strcmp(tokens[i],"/")==0)StackPush(&st,num2/num1);
  }
  else
  {
  StackPush(&st,atoi(token));}
  }

return StackTop(&st);
StackDestroy(&st);



 
}

二叉树篇

单值二叉树

bool isUnivalTree(struct TreeNode* root) {
if(root==NULL)
return true;
else if(root->left&&root->left->val!=root->val)
return false;
else if(root->right&&root->right->val!=root->val)
return false;

return isUnivalTree(root->left)&&isUnivalTree(root->right);





    
}

对称二叉树

bool _isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot) {
if(leftroot==NULL&&rightroot==NULL)
return true;
if(leftroot==NULL||rightroot==NULL)
return false;
if(leftroot->val!=rightroot->val)
return false;
return  _isSymmetric(leftroot->left,rightroot->right)&&_isSymmetric(leftroot->right,rightroot->left);




    
}



bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left,root->right);
}

二叉树前序遍历

int BinaryTreeSize(struct TreeNode* root)
{return root==NULL?0:BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
void  aapreorderTraversal(struct TreeNode* root,int*a,int*pi)
{if(root==NULL)
return ;
a[(*pi)++]=root->val;
aapreorderTraversal(root->left,a,pi);
aapreorderTraversal(root->right,a,pi);
}




int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize= BinaryTreeSize(root);
int*a=(int*)malloc(*returnSize*sizeof(int));
int i=0;
aapreorderTraversal(root,a,&i);
return a;
free(a);





    
}

中序遍历

int BinaryTreeSize(struct TreeNode* root)
{return root==NULL?0:BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;
}
void  aapreorderTraversal(struct TreeNode* root,int*a,int*pi)
{if(root==NULL)
return ;

aapreorderTraversal(root->left,a,pi);
a[(*pi)++]=root->val;
aapreorderTraversal(root->right,a,pi);
}




int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize= BinaryTreeSize(root);
int*a=(int*)malloc(*returnSize*sizeof(int));
int i=0;
aapreorderTraversal(root,a,&i);
return a;
free(a);





    
}

后序遍历

 int BinaryTreeSize(struct TreeNode* root)
 {return root==NULL?0:BinaryTreeSize(root->left)+BinaryTreeSize(root->right)+1;

 }
void aapostorderTraversal(struct TreeNode* root, int*a,int*pi)
{if(root==NULL)
return ;
aapostorderTraversal(root->left,a,pi);
aapostorderTraversal(root->right,a,pi);
a[(*pi)++]=root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize=BinaryTreeSize(root);
int *a=(int*)malloc(*returnSize*sizeof(int));
if(a==NULL)
{perror("malloc fail");}
int i=0;
aapostorderTraversal(root, a,&i);
return a;

}

另一个子树

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left, q->left)&&isSameTree(p->right,q->right);





}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
if(isSameTree(root,subRoot ))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);






}

二叉树遍历

#include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTreeNode {
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;
BTNode* BinaryTreeCreate(char* a, int* pi)
{if(a[*pi]=='#')
{(*pi)++;
   return NULL;}
BTNode* root=(BTNode*)malloc(sizeof(BTNode));
if(root==NULL)
perror("malloc fail");
root->data=a[(*pi)++];
root->left=BinaryTreeCreate(a,pi);
root->right=BinaryTreeCreate(a,pi);
return root;
}
void  InOrder(BTNode* root)
{if(root==NULL)
 return ;
 InOrder(root->left);
  printf("%c ",root->data);
 InOrder(root->right);



}


int main() {
    char arr[100];
    scanf("%s", arr);
    int i=0;
BTNode*bk= BinaryTreeCreate(arr,&i);
InOrder(bk);












}

相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left, q->left)&& isSameTree(p->right, q->right);




}

翻转二叉树

struct TreeNode* invertTree(struct TreeNode* root) {
if(root==NULL)
return NULL;
struct TreeNode* rootleft=invertTree(root->left);
struct TreeNode* rootright=invertTree(root->right);
root->left=rootright;
root->right=rootleft;
return root;

}