#94 二叉树的中序遍历

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>



//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().
 */
void inorder(struct TreeNode *root, int *result, int *returnSize)
{
    if(!root) return;
    inorder(root->left, result, returnSize);
    result[(*returnSize)++] = root->val;
    inorder(root->right, result, returnSize);
    

}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *result = malloc(100 * sizeof(int));
    memset(result, 0, 100 * sizeof(int));
    inorder(root, result, returnSize);
    return result;
}
int main()
{
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = NULL;
    struct TreeNode *right = malloc(sizeof(struct TreeNode));
    right->val = 2;
    struct TreeNode *tmp = malloc(sizeof(struct TreeNode));
    tmp->val = 3;
    tmp->left = NULL;
    tmp->right = NULL;
    right->right = NULL;
    right->left = tmp;
    root->right = right;
    
    int returnSize = 0;
    int *result = inorderTraversal(root, &returnSize);
    int i;
    for(i = 0; i<returnSize; ++i)
    {
        printf("%d, ", result[i]);
    }
    return 0;
}