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].
Note: Recursive solution is trivial, could you do it iteratively?
Subscribe to see which companies asked this question
解答
注意空树的情况……
/**
* 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) {
, i = ;
);
];
if(NULL == root){
*returnSize = i;
return return_array;
}
stack[++top] = root;
!= top){
root = stack[top--];
return_array[i++] = root->val;
if(NULL != root->right)
stack[++top] = root->right;
if(NULL != root->left)
stack[++top] = root->left;
}
*returnSize = i;
return return_array;
}