Given a binary tree, return the preorder traversal of its nodes' values.
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
递归实现
/**
* 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;
}