【数据结构】C语言算法练习题——前序遍历

题目链接：

力扣https://leetcode.cn/problems/binary-tree-preorder-traversal/

解题思路：

1. 首先自定义一个可以求所给二叉树结点的函数

2. 然后需要动态开辟数组（这个数组便是题目要求输出的最终结果），因为静态数组出了作用域便会被销毁，而动态内层分配除了 free 之外，它都不会被销毁

3. 不能对题目中所给的函数进行递归，因为我们在这个函数里面有 malloc ，如果对其函数进行递归，则每一次的调用都要进行 malloc ，从而浪费了空间

解决的办法是：

再次自定义一个函数

4. 没有 void*，只有 void 

代码实现：

int TreeSize (struct TreeNode *root)//该函数用来求题目中所给二叉树的结点个数
{
    return root == NULL? 0 : TreeSize(root->left)+TreeSize(root->right)+1;//+1的原因是要算上根结点
}

void PrevOrder(struct TreeNode *root,int *a,int *i)//用来递归的前序遍历函数，其中的 i 是遍历过程中数组的下标

{
    if(root == NULL)
    {
        return;
    }

    //当二叉树不为空树时：
   a[(*i)++] = root->val;//要把结点的值按前序遍历的顺序放入动态数组 a 中
    PrevOrder(root->left,a,i);//注意这里不是 &i，因为 i 此时已经是地址了
    PrevOrder(root->right,a,i);//前序遍历的顺序

}
int* preorderTraversal(struct TreeNode* root, int* returnSize)//这里的returnSize的类型是int*的原因是：形参的改变无法影响实参
{
    *returnSize = TreeSize(root);
    int *a = (int *)malloc(*returnSize *sizeof(int));
    int i = 0;
    PrevOrder(root,a,&i);//注意这里是 &i

    return a;
}