【LeetCode刷题指南】--二叉树的后序遍历，二叉树遍历

草莓熊Lotso

发布于 2025-10-29 14:08:46

1670

文章被收录于专栏：C++/LinuxC++/Linux

🔥个人主页：@草莓熊Lotso 🎬作者简介：C++研发方向学习者 📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》 ⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在之前的C语言刷题集中我们刷了很多IO类型的基础编程题，但是随着数据结构往后的学习以及企业面试的要求，我们还需要对接口型的题目进行练习，博主在这里准备了新的《LeetCode刷题指南》专栏给大家分享一些我自己在力扣上面写过的题目，提供一些我的解题思路。个人实力有限，欢迎大家补充和指正。

一.二叉树的后序遍历

题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

题目描述：

题目示例：

思路： 后序遍历，动态开辟数组

解题过程：

1. returnsize表示要返回的数组的大小，我们这里需要动态开辟数组所申请的空间也是 returnsize*sizeof(int)，这个我们需要实现一个TreeSize函数来解决(结点个数=根节点+左子树节点个数+右子树节点个数)

2.注意我们代码里面传的i需要传地址，这里其实就是把我们之前实现的后序遍历的函数参数改了一下，然后在函数里的打印换成了用数组存储

3.最后都结束了之后，直接返回ans就可以了

复杂度：

时间复杂度: O(n)
空间复杂度: O(n)

代码实现：

/**
 * 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().
 */
typedef struct TreeNode TreeNode;
void PostOrder(TreeNode*root,int*ans,int*pi)
{
    if(root==NULL)
    {
        return;
    }

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

int TreeSize(TreeNode*root)
{
    if(root==NULL)
    {
        return 0;
    }
    return 1+TreeSize(root->left)+TreeSize(root->right);
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=TreeSize(root);
    int*ans=(int*)malloc(sizeof(int)*(*returnSize));

    int i=0;
    PostOrder(root,ans,&i);
    return ans;
}

二.二叉树遍历

题目链接：二叉树遍历_牛客题霸_牛客网

题目描述：

题目示例：

解题过程：

1.定义一个二叉树的结构，然后将读取的输入字符串保存在数组中

2.根据前序遍历序列创建一个树，如果遇到#就直接*pi++然后返回，其它的时候就是申请节点(这个很简单就不讲了，传的参数是arr[(*pi)++]，注意是后置++)，然后递归创建左孩子节点和右孩子节点(核心思想和前序遍历相似，可以参考)，递归创建结束后返回root节点。

3.再调用中序遍历，传的是之前返回的创建完后的root，这个题就结束了。

4.本题的难点就是全过程都要自己实现，思路一定要非常明确

具体过程如图所示：

复杂度：

时间复杂度：O(n)
空间复杂度：O(n)

代码实现：

#include <stdio.h>
#include<stdlib.h>

typedef struct BinaryTree
{
    char data;
    struct BinaryTree*left;
    struct BinaryTree*right;
}BTNode;

BTNode*BuyNode(char ch)
{
    BTNode*newcode=(BTNode*)malloc(sizeof(BTNode));
    if(newcode==NULL)
    {
        perror("malloc fail!");
        exit(-1);
    }

    newcode->data=ch;
    newcode->left=newcode->right=NULL;
    return newcode;
}
//构建二叉树
BTNode*CreateTree(char*arr,int*pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode*root=BuyNode(arr[(*pi)++]);
    root->left=CreateTree(arr,pi);
    root->right=CreateTree(arr,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[101];
    scanf("%s",arr);
   //根据先序遍历创建一个树
   int i=0;
   BTNode*root=CreateTree(arr,&i);
   //中序遍历
   InOrder(root);
}

往期回顾：

【LeetCode刷题指南】--队列实现栈，栈实现队列

【LeetCode刷题指南】--单值二叉树，相同的树

【LeetCode刷题指南】--二叉树的前序遍历，二叉树的中序遍历

【LeetCode刷题指南】--对称二叉树，另一颗树的子树

结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。

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

原始发表：2025-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树