题目
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?
分析
中序遍历二叉树，很简单的递归，先输出左节点，然后输出右节点。
题目说可以使用迭代，一般递归够可以转化为迭代。不过需要一个堆栈，记录一些列的左节点。
/**
* 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;
}
