/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    int *result = NULL;
    if (NULL == root)
        return NULL;
    /*先申请一个int，保存根节点*/
    result = (int *)malloc(sizeof(int));
    *result = root->val;


    int *leftarr=NULL, *rightarr=NULL, leftsize=0, rightsize=0;
    int i=0,j=0;
    
    if(root->left)
        leftarr = preorderTraversal(root->left,&leftsize);
    
    if(root->right)
        rightarr = preorderTraversal(root->right,&rightsize);
    
    *returnSize = 1 + leftsize  + rightsize;
    
    if(leftsize > 0 || rightsize > 0)
        result = (int *)realloc(result,*returnSize * sizeof(int));
    
    /*拷贝letfarr与rightarr指向的内容到result中*/
    for(;i < leftsize;i++)
        result[i+1] = leftarr[i];
    
    /*存放右子树*/
    for(;j<rightsize;j++)
        result[i+1+j] = rightarr[j];
    
    /*释放内存*/
    if(leftsize > 0)
        free(leftarr);
    
    if(rightsize > 0)
        free(rightarr);
    
    return result;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    int *result = NULL;
    if (root == NULL)
        return result;

    *returnSize = 0;

    struct TreeNode **stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *));
    struct TreeNode *pop;
    int cur = 0;
    stack[cur++] = root;

    while(cur > 0)
    {
        result = (int *)realloc(result, (*returnSize + 1) * sizeof(int));
        pop = stack[--cur];
        result[*returnSize] = pop->val;
        *returnSize += 1;
        
        if(pop->right)
        {
            stack = (struct TreeNode **)realloc(stack,sizeof(struct TreeNode *) * (cur + 1));
            stack[cur++] = pop->right;
        }
        
        if(pop->left)
        {
            stack = (struct TreeNode **)realloc(stack,sizeof(struct TreeNode *) * (cur + 1));
            stack[cur++] = pop->left;
        }
    }
    free(stack);
    return result;

}