首页 > 试题广场 >

二叉树的中序遍历

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

数据范围：树上节点数满足 ，树上每个节点的值满足 -1000 \le val \le 1000
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,2,#,#,3}

输出

[2,3,1]

说明
示例2

输入

{}

输出

[]
示例3

输入

{1,2}

输出

[2,1]

说明
示例4

输入

{1,#,2}

输出

[1,2]

说明

备注:
树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内

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

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

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = malloc(sizeof(int) * 1001);
    int count = 0;
    inOrder(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:48:56 回复(0)
C
A202302282044461头像 A202302282044461
 int count = 0;
 int arr[1000];
 void in_order(struct TreeNode * root, int * arr)
 {
    if(root != NULL)
    {
        in_order(root->left, arr);
        arr[count++] = root->val;
        in_order(root->right, arr);
    }
 }
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    in_order(root, arr);
    *returnSize = count;
    return arr;
}
发表于 2023-09-13 13:02:27 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈

int* inorderTraversal(struct TreeNode* root, int* returnSize )
{
    // write code here
    int *arr = (int*)malloc(sizeof(int)*1000);
    struct TreeNode*adress[1000];
    int i=0;
    int j=0;
    struct TreeNode*p=root;
    while(1)
    {
        while(p)
        {
            adress[i]=p;
            i++;
            p=p->left;
        }
        i--;
        if(i<0)
        {
            break;
        }
        *(arr+j)=adress[i]->val;
        j++;
        p=adress[i]->right;
    }
    *returnSize=j;
    return arr;
}
发表于 2023-06-25 00:16:03 回复(0)
C
小小小孩头像 小小小孩 
struct TreeNode* stack[1000]; //作为栈使用，栈底是下标0
int stack_top = -1;
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    int* ret_arr = NULL;
    *returnSize = 0;
    if (!root)
        return ret_arr;
    int tmp[1000] = {0};
    int i = 0;
    while (root) {
        if (root->left)
        {
            stack[++stack_top] = root;
            root = root->left;
            stack[stack_top]->left = NULL; //一定要NULL，否则会死循环
        }
        else
        {
            tmp[i++] = root->val;
            if(root->right)
                root = root->right;
            else
            {
                 if (stack_top >= 0)
                 {
                    printf("stack_top: %d\n",stack_top);
                    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:59:29 回复(0)
C
JayneChou头像 JayneChou 
int pre_sequence[1000] = {0}, i = 0;
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    int top_stack = -1;
    struct TreeNode* stack[1000], *p;
    if(root != NULL){
        stack[++top_stack] = root;
    }
    while (top_stack != -1) {
        if(stack[top_stack]->right != NULL){
            stack[top_stack + 1] = stack[top_stack];
            stack[top_stack] = stack[top_stack]->right;
            stack[++top_stack]->right = NULL;
        }
        if(stack[top_stack]->left != NULL){
            stack[top_stack + 1] = stack[top_stack]->left;
            stack[top_stack++]->left = NULL;
        } else {
            pre_sequence[i++] = stack[top_stack]->val;
            top_stack--;
        }
    }
    *returnSize = i;
    return pre_sequence;
}

发表于 2023-02-24 11:45:19 回复(0)
C
徐拾肆头像 徐拾肆
void inorder(struct TreeNode* root,int* ret,int* returnSize)
{
    if(root!=NULL){
        inorder(root->left, ret, returnSize);
        ret[(*returnSize)++]=root->val;
        inorder(root->right, ret, returnSize);
    }
}
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    int*ret=(int*)malloc(sizeof(int)*1000);
    *returnSize=0;
    inorder( root, ret,returnSize);
    printf("retsize=%d",*returnSize);
    return ret;
}
发表于 2022-11-09 23:51:26 回复(0)
C
牛客129497907号头像 牛客129497907号
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
     int *arr = (int *)malloc(sizeof(int)*1024);
    *returnSize = 0;
    int top = -1;
    struct TreeNode* stack[1024];
    struct TreeNode*p = root;
    //stack[top] = root;//根结点入栈
    while(top != -1 || p != NULL)
    {
        while(p!=NULL)
        {
            stack[++top] = p;
            p = p->left;
        }
        if(top != -1)
        {
            p = stack[top--];
            arr[(*returnSize)++] = p->val;
            p = p->right;
        }
    }
    return arr;
}
发表于 2022-04-08 02:10:26 回复(0)
C
Chromium丶头像 Chromium丶 
static int count = 0;
void inOrder(struct TreeNode* root,int *a){
    if(root != NULL){
        inOrder(root->left, a);
        a[count++] = root->val;
        inOrder(root->right, a);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    int *a = (int*)malloc(sizeof(int)*1001);
    inOrder(root, a);
    *returnSize = count;
    return a;
    // write code here
}

发表于 2022-03-17 16:18:13 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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