【OJ】二叉树的遍历-2. 94二叉树的中序遍历

2.1 分析

这题和上面前序遍历是一样的思路，就是把遍历节点的顺序该一下，其他都相同。
也就将遍历的函数改为：先遍历左子树，然后数组来记录中间root的val值，再是右子树。

void Inorder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    Inorder(root->left,arr,i);
    arr[(*i)++]=root->val;
    Inorder(root->right,arr,i);
}

2.2 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int Size(struct TreeNode* root)
{
    return root==NULL?0:Size(root->left)+Size(root->right)+1;
}
void Inorder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    Inorder(root->left,arr,i);
    arr[(*i)++]=root->val;
    Inorder(root->right,arr,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=Size(root);
    int* arr=(int*)malloc(*returnSize*sizeof(int));
    int i=0;
    Inorder(root,arr,&i);
    return arr;
}