首页 > 试题广场 >

二叉树的后序遍历

[编程题]二叉树的后序遍历
  • 热度指数：61502 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 ，二叉树节点的值满足 ，树的各节点的值各不相同

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图
示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿 
void postorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) {
    if(root->left!=NULL) 
        postorderTraver(root->left, res, StaticReturnSize);
    if(root->right!=NULL) 
        postorderTraver(root->right, res, StaticReturnSize);
    res[(*StaticReturnSize)++] = root->val;
}    
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    static int res[1000]={0}, StaticReturnSize=0;
    if(root==NULL) 
        return NULL;
    postorderTraver(root, res, &StaticReturnSize);
    *returnSize = StaticReturnSize;
    return res;
}

编辑于 2024-03-16 16:01:01 回复(0)
C
就要上岸了的秋招人很用心头像 就要上岸了的秋招人很用心 
void postOrder(struct TreeNode* root, int** a, int* count) {
    if (root != NULL) {
        postOrder(root->left, a, count);
        postOrder(root->right, a, count);
        (*a)[(*count)++] = root->val;
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = malloc(sizeof(int) * 1001);
    int count = 0;
    postOrder(root, &a, &count);
    *returnSize = count;
    int* result = malloc(sizeof(int) * count);
    memcpy(result, a, sizeof(int) * count);
    free(a);
    return result;
}

编辑于 2024-03-11 18:46:09 回复(0)
C
陈让然头像 陈让然
方法一：递归 
 int count=0;
 int arr[101];

void postOrder(struct TreeNode*root,int*arr)
{
    if(root)
    {
        postOrder(root->left,arr);
        postOrder(root->right,arr);
        arr[count++]=root->val;
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    // write code here
    postOrder(root,arr);
    *returnSize=count;
    return arr;
}
方法二：栈 
struct TreeNode*stack[100];
int arr[101];
int count=0;
int top=-1;

//记录上一个访问的节点
struct TreeNode* prev = NULL;

//入栈
void push(struct TreeNode*node)
{
    stack[++top]=node;
}
//出栈
struct TreeNode* pop(void)
{
    return stack[top--];
}
//后序遍历  左->右->根
//用栈实现，先进后出
int* postorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    // write code here
    if(!root)
    {
        *returnSize=0;
        return NULL;
    }

    while(root||top!=-1)
    {
        while(root)
        {    
            push(root);
            root=root->left;
        }

        root=stack[top];

        //如果栈顶元素的右节点为空或者已经访问过，则可以访问根节点
        if (!root->right || root->right == prev) 
        {
            //根节点存在，保存val
            arr[count++] = root->val;
            //记录上一个访问的节点
            prev = root;
            //栈顶元素出栈
            root = pop();
            //将根节点置为NULL，避免再次访问
            root = NULL;
        } 
        else 
        {
            //开始遍历右节点
            root = root->right;
        }

    }
    *returnSize=count;
    return arr;  
}
发表于 2023-09-17 16:08:39 回复(0)
C
A202302282044461头像 A202302282044461
 int count = 0;
 int arr[100];
 void post_order(struct TreeNode * root, int * arr)
 {
    if (root != NULL) {
        post_order(root->left, arr);
        post_order(root->right, arr);
        arr[count++] = root->val;
    }
 }
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    post_order(root, arr);
    *returnSize = count;
    return arr;
}
发表于 2023-09-13 13:05:46 回复(0)
C
小小小孩头像 小小小孩 
struct TreeNode* stack[100]; //作为栈使用，栈底是下标0
int stack_top = -1;
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    int* ret_arr = NULL;
    *returnSize = 0;
    if (!root)
        return ret_arr;
    int tmp[100] = {0};
    int i = 0;
    struct TreeNode* l_ptr = NULL;
    struct TreeNode* r_ptr = NULL;
    while (root) {
        if (root->right || root->left)
        {
            stack[++stack_top] = root;
            l_ptr = root->left;
            r_ptr = root->right;
            stack[stack_top]->left = NULL;
            stack[stack_top]->right = NULL;
            if(r_ptr)
                stack[++stack_top] = r_ptr;
            if(l_ptr)
                root= l_ptr;
            else
            {
                if (stack_top >= 0)
                    root = stack[stack_top--];
                else
                    root = NULL;
            };
        }
        else {
            tmp[i++] = root->val;
            if (stack_top >= 0)
                root = stack[stack_top--];
            else
                root = NULL;
        }
    }
    *returnSize = i;
    ret_arr = malloc(sizeof(int) * i);
    if (!ret_arr)
        return NULL;
    memset(ret_arr, 0, i * sizeof(int));
    for (int j = 0; j < i; j++)
        ret_arr[j] = tmp[j];
    return ret_arr;
}

发表于 2023-03-04 00:58:40 回复(0)
C
JayneChou头像 JayneChou 
int postArr[100];
void postTraversal(struct TreeNode* root, int* returnSize, int* p){
    if(root != NULL){
        postTraversal(root->left, returnSize, p);
        postTraversal(root->right, returnSize, p);
        p[(*returnSize)++] = root->val;
    }
 }
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    *returnSize = 0;
    postTraversal(root, returnSize, postArr);
    return postArr;
}

发表于 2023-02-24 11:59:20 回复(0)
C
徐拾肆头像 徐拾肆
C语言采用递归求
void postorder(struct TreeNode* root,int* ret,int* returnSize)
{
    if(root!=NULL){
        postorder(root->left, ret, returnSize);
        postorder(root->right, ret, returnSize);
        ret[(*returnSize)++]=root->val;
    }
}
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    int*ret=(int*)malloc(sizeof(int)*1000);
    *returnSize=0;
    postorder( root, ret,returnSize);
    printf("retsize=%d",*returnSize);
    return ret;
}
发表于 2022-11-09 23:55:32 回复(0)
C
牛客310019324号头像 牛客310019324号
static int count=0;//定义一个整型变量，并对其进行初始化，一定注意在进行变量的定义结束以后，我们要对变量进行初始化以后才可以进行使用
//我们要创建一个数组来存放遍历二叉树的结点
void Postraversal(struct TreeNode* root,int* a)
{//遇到空结点就返回,我们只对其不为空时做操作
    if(root!=NULL)
    {
        Postraversal(root->left,a);
        Postraversal(root->right,a);
        a[count++]=root->val;
    }
    
}
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    //对我们所使用的a变量进行定义，因为其存放整型的元素
   int*a=(int*)malloc(sizeof(int)*101);//注意在定义变量的时候，要有变量类型,因为要存放数据，所以要表明可以存储多少的数据
   if(!a)
   {
       return NULL;
   }
    Postraversal(root, a);//将其所需要的参数传进去
    *returnSize = count;
    return a;
    
}
发表于 2022-08-25 09:28:54 回复(0)
C
阿金要努力头像 阿金要努力 
static int count=0;
int TreeSize(struct TreeNode* root)
{
    if(!root)
        return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
void  PostOrderTree(struct TreeNode* root,int* arr)
{
    if(root)
    {
        PostOrderTree(root->left, arr);
        PostOrderTree(root->right, arr);
        arr[count++]=root->val;
    }
}
int* postorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    int num=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*num);
    *returnSize=num;
    PostOrderTree(root,arr);
    return arr;
}

发表于 2022-05-02 13:35:00 回复(0)
C
无敌俊俊头像 无敌俊俊
C 语言
递归版 
typedef struct TreeNode TreeNode;
void Last(TreeNode *root,int *ret,int *retSize)
{
    if(!root)
    {
        return;
    }
    Last(root->left,ret,retSize);
    Last(root->right,ret,retSize);
    ret[(*retSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    int *ret = (int *)malloc(sizeof(int)*101);
    
    *returnSize = 0;
    Last(root,ret,returnSize);
    
    return ret;
}



发表于 2022-03-14 15:58:44 回复(0)
提交观点

问题信息

树 dfs 递归 广度优先搜索(BFS)
难度：
10条回答 3662浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号