首页 > 试题广场 >

二叉树的前序遍历

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

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

示例 1：


示例1

输入

{1,#,2,3}

输出

[1,2,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
Daniel_shark头像 Daniel_shark
void traverse(int *res, struct TreeNode* root, int* returnSize)
{
    if (root == NULL) {
        return;
    }
    res[(*returnSize)++] = root->val;
    traverse(res, root->left, returnSize);
    traverse(res, root->right, returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res = (int *)calloc(101, sizeof(int));
    traverse(res, root, returnSize);
    return res;
}
发表于 2025-05-27 16:06:11 回复(0)
C
StellarVibes头像 StellarVibes
void fuc(struct TreeNode* root, int* arr,int * count)
{
    if (root == NULL)
    {
        return;
    }
    arr[*count] = root->val;
    //printf("%d ",arr[*count]);
    //printf("%d\n",*count);
    (*count)++;
    fuc(root->left, arr,count);
   
    fuc(root->right, arr,count);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* arr = (int*)malloc(sizeof(4)*1000);
    int count = 0;
    fuc(root, arr,&count);
    //while(*arr)
    //{
        //printf("%d ",*arr);
        //arr++;
    //}
    *returnSize=count;
    return arr;
}
发表于 2024-12-14 18:24:57 回复(1)
C
一个优雅的程序猿头像 一个优雅的程序猿 
void preorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) {
    res[(*StaticReturnSize)++] = root->val;
    if(root->left!=NULL) 
        preorderTraver(root->left, res, StaticReturnSize);
    if(root->right!=NULL) 
        preorderTraver(root->right, res, StaticReturnSize);
}    
int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    static int res[100]={0}, StaticReturnSize=0;
    if(root==NULL) 
        return NULL;
    preorderTraver(root, res, &StaticReturnSize);
    *returnSize = StaticReturnSize;
    return res;
}

编辑于 2024-03-16 15:55:35 回复(0)
C
陈让然头像 陈让然
方法一：递归 
#include <stdio.h>
#include <stdlib.h>
//记录结点个数
int count=0;
//存储结点值，方便返回
int arr[101];
//先根后左右
void preOrder(struct TreeNode*root,int*arr)
{
    if(root)
    {
        arr[count++]=root->val;
        preOrder(root->left, arr);
        preOrder(root->right, arr);
    }
}
int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    preOrder(root, arr);
    //便利侯，关系结点数量
    *returnSize=count;
    return arr;
}
方法二：栈实现，按先序顺序先入栈结点，直到无左结点，再出栈，对右节点遍历 
#include <stdio.h>
#include <stdlib.h>
struct TreeNode* stack[100]; //作为栈使用，栈底是下标0
int stack_top = -1;
//入栈
void push(struct TreeNode* node) 
{
    stack[++stack_top] = node;
}
//出栈
struct TreeNode* pop() 
{
    return stack[stack_top--];
}
//先序遍历  根->左->右
//用栈实现，先进后出
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) 
    {
        *returnSize = 0;
        return NULL;
    }
    
    int* ret_arr = malloc(sizeof(int) * 100);
    int i = 0;
    
    while (root || stack_top != -1) 
    {
        //从根节点开始
        while (root) 
        {
            //根节点存在，保存val
            ret_arr[i++] = root->val;
            //每个根节点入栈
            push(root);
            //根节点左移，也就是每次先将左值保存
            //无左结点，跳出对右节点操作
            root = root->left;
        }
        //根节点等于栈顶元素，即上一个无左结点的节点
        root = pop();
        //开始遍历右节点
        root = root->right;
    }
    
    *returnSize = i;
    return ret_arr;
}
发表于 2023-09-17 15:39:07 回复(0)
C
ت20181024193444头像 ت20181024193444 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param root TreeNode类 
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
static int count = 0;
static int a[101];

void preOrder(struct TreeNode* root, int* a){
    if(root!=NULL){
        // printf("%d,", root->val);
        a[count++]=root->val;
        preOrder(root->left, a);
        preOrder(root->right, a);
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    preOrder(root, a);
    *returnSize = count;
    return a;
}

发表于 2023-03-29 00:35:45 回复(0)
C
小小小孩头像 小小小孩 
struct TreeNode* stack[100]; //作为栈使用，栈底是下标0
int stack_top = -1;
int* preorderTraversal(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;
    while(root)
    {
        if(root->right)
            stack[++stack_top] = root->right;
        tmp[i++] = root->val;
        printf("%d ",tmp[i]);
        if(root->left)
            root = root->left;
        else
        {
            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-03 22:52:59 回复(0)
C
靠谱的牛牛摆烂了头像 靠谱的牛牛摆烂了
returnsize存储的是一维数组的列数，为什么要说返回数组行数？
typedef struct TreeNode TNode ;
 int i = 0;
 int prestr[100];
 void pre(TNode* root, int a[])
 {
    if (root != NULL) {
        a[i] = root->val;
        i++;
        pre(root->left,a);
        pre(root->right,a);
    }
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    pre(root, prestr);
    *returnSize = i;
    return prestr;
}

发表于 2023-02-18 10:38:46 回复(0)
C
阿金要努力头像 阿金要努力 
static int num=0;
void PreOrder(struct TreeNode* root,int* arr)
{
    if(root)
    {
        arr[num++]=root->val;
        PreOrder(root->left, arr);
        PreOrder(root->right, arr);
    }
}
int TreeSize(struct TreeNode* root)
{
    if(!root)
    {
        return 0;
    }
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    int count=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*count);
    PreOrder(root,arr);
    *returnSize=count;
    return arr;
}

发表于 2022-05-02 12:50:30 回复(0)
C
和覅wEJVB头像 和覅wEJVB
int TreeSize(struct TreeNode* root)
{
   if(root==NULL)
   {
       return 0;
   }
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root, int* a,int *i) 
{
    if(root==NULL)
    {
        return ;
    }
    a[*i]=root->val;
    ++(*i);
    preorder(root->left,a,i);
    preorder(root->right,a,i); 
}
int* preorderTraversal(struct TreeNode* root, int* returnSize ) 
{  
    int i=0; 
    int size=TreeSize(root);
    int* a=(int*)malloc(size*sizeof(int));
    preorder(root,a,&i);
    *returnSize=size;
    return a;
}
发表于 2022-04-13 21:42:58 回复(0)
C
Chromium丶头像 Chromium丶 
static int count = 0;
void preOrder(struct TreeNode *root,int *a){
    if(root != NULL){
        a[count++] = root->val;
        preOrder(root->left, a);
        preOrder(root->right, a);
    }
}


int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    int *a = (int*)malloc(sizeof(int)*101);
    preOrder(root, a);
    *returnSize = count;
    return a;
}

发表于 2022-03-17 16:12:04 回复(3)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的前序遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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