leetcode：前序遍历

用户10925563

发布于 2024-06-04 13:13:49

620

发布于 2024-06-04 13:13:49

文章被收录于专栏：c/c++&&linux

题目描述

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目分析

这道题的难点在于，前序遍历一遍之后需要将数值存在数组里，returnsize就是数组的大小

所以我们先构建一个函数来计算节点的个数

然后我们前序遍历，遍历的同时将数值存到数组里

最后再函数里先保存数组的大小，开辟一个数组，用i来控制数组往后走，为了防止局部变量出函数销毁，我们取i的地址

代码示例

/**
 * 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().
 */
int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//int i=0;
void preorder(struct TreeNode*root,int *a,int *i)
{
    if(root==NULL)
        return;
    a[(*i)++]=root->val;
    preorder(root->left,a,i);
    preorder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    int *a=(int*)malloc(sizeof(int)*n);
    *returnSize=n;
    int i=0;
    preorder(root,a,&i);
    return a;
}