题目

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;
}