我要招人

去企业版

首页 > 试题广场 >

二叉树的前序遍历

[编程题]二叉树的前序遍历

热度指数：102422 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你二叉树的根节点 root ，返回它节点值的前序遍历。

数据范围：二叉树的节点数量满足 $1 \le n \le 100 \$ ，二叉树节点的值满足 $1 \le val \le 100 \$ ，树的各节点的值各不相同

示例 1：

示例1

输入

{1,#,2,3}

输出

[1,2,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

一个优雅的程序猿

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)

陈让然

方法一：递归
#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)

ت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)

小小小孩

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)

靠谱的牛牛摆烂了

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)

阿金要努力

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)

和覅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)

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)