Leetcode每日一题

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

这道题目需要我们自行进行创建一个数组，题目也给出我们需要自己malloc一个数组来存放，这样能达到我们遍历的效果，我们来看看他的接口函数给的是什么。

可以看到的是这个接口函数给了一个root就是根节点的意思，但是这里的returnsize是什么意思可能有问题？

其实returnsize这里虽然给的是指针，是因为我们函数栈帧创建和销毁的时候，形参只是实参的一份临时拷贝，这样的话，我们就算给returnsize赋值进行改变，也不能改变他的值

这里的returnsize是我们需要在这个函数外面统计数组的个数

我们来看这个题目的第一个问题就是我们要开辟一个数组，开辟数组的话我们是不是得知道这个数组空间有多大才行，所以我们得先写一个函数就是统计节点的函数，那这个函数其实就是遍历数组，用的就是递归的方式进行遍历。

int BinaryTreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

这个就是我们来统计有多少节点的函数，思想就是我们遇到空的时候就返回，不是空的时候就是得返回一个节点。下面我们就只需要在题目给的接口函数进行调用，然后malloc一个数组出来就行。

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = BinaryTreeSize(root);
    int* arry = (int*)malloc(sizeof(int)*n);
    assert(arry);
    int size = 0;
    _preorderTraversal(root, arry, &size);
    *returnSize = n;
    return arry;


}

然后我们需要做的就是实现我们遍历函数的内容，其实很简单，因为前序遍历的时候是先中间节点，然后是他的左孩子和右孩子，所以我们的递归方法就出来了。

void _preorderTraversal(struct TreeNode* root, int* a,int* pi)
{
    if(root == NULL)
    {
        return ;
    }
    a[(*pi)++] = root->val;
    _preorderTraversal(root->left, a, pi);
    _preorderTraversal(root->right, a, pi);


}

这里需要注意的地方就是pi这个值我们是需要取出他的地址进行，因为如果不是地址的话，我们每次函数递归的时候建立函数栈帧的时候就是会有问题，每次都是局部变量，所以我们得用他的地址，这个也就是为什么我们的size是取地址传进来的，而不是直接传0，因为传0的话，形参只是实参的一份临时拷贝，改变形参并不会对实参有任何的影响。

谢谢大家观看，我们下次再见。