題目
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
分析
中序遍歷二叉樹，很簡單的遞歸软棺，先輸出左節(jié)點阁将，然后輸出右節(jié)點。
題目說可以使用迭代侮措，一般遞歸夠可以轉(zhuǎn)化為迭代懈叹。不過需要一個堆棧，記錄一些列的左節(jié)點分扎。
/**
* 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 inTraversal(struct TreeNode * node,int *returnSize,int *ans)
{
if(node!=NULL&&node->left!=NULL)
{
inTraversal(node->left,returnSize,ans);
}
if(node!=NULL)
{
ans[*returnSize]=node->val;
*returnSize=*returnSize+1;
}
if(node!=NULL&&node->right!=NULL)
{
inTraversal(node->right,returnSize,ans);
}
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int *ans=(int *)malloc(sizeof(int)*10000);
*returnSize=0;
inTraversal(root,returnSize,ans);
return ans;
}
