3.1 144. Binary Tree Preorder Traversal (Medium)

Given a binary tree, return the preorder traversal 
of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].```

Preorder Traversal 前序遍歷 順序是：根、左子樹、右子樹,就是DFS. 解法有遞迴、迴圈跟Morris Traversal Algorithm。  

為什麼要宣告一個那麼大array，因為它題目就是那麼煩，為什麼每題C都要用malloc ， 在不知道題相的樹到底會多大情況下，先隨便告一個很大的空間試試online judge 會不會過。  

```c
/**
 * 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().
 */



void preOrder(struct TreeNode* n,int array[], int *i)
{

    if(n!=NULL){

        array[(*i)]=n->val;
        (*i)++;

        preOrder(n->left,array,i);
        preOrder(n->right,array,i);
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
     int *nodes;
     int array[1000];
     int i=0;

     if(root ==NULL)
        return 0;

     /*preorder 尋訪結點，把結果存到array裡*/   
     preOrder(root,array,&i);

     /*照題目要求宣告一個空間，把結果傳回去*/
     *returnSize=i;
     nodes=(int *)malloc(i*sizeof int);
     memcpy(nodes,array,i*sizeof int);

     return nodes;
}