[LeetCode] 94. 二叉树的中序遍历

[Animenzzzz]

题目描述：

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路：这题使用C的话，对于值的暂存有些麻烦，没有栈的系统库。看了网上的写法：https://www.52coder.net/post/LeetCode94

C解题：

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *result = NULL;
    if(!root){
        *returnSize=  0;
        return NULL;
    } 
    int *leftArr = NULL;
    int *rightArr = NULL;
    int leftindex = 0,rightindex = 0,i = 0,j = 0;
    if(root->left){
        leftArr = inorderTraversal(root->left,&leftindex);
    }
    if(root->right){
        rightArr = inorderTraversal(root->right,&rightindex);
    } 
    *returnSize = leftindex + 1 + rightindex;
    result = (int *)calloc((*returnSize),sizeof(int));
    for(;i<leftindex;i++)
        result[i] = leftArr[i];
    /*存放根节点*/
    result[i++] = root->val;
    /*存放右子树*/
    for(;j<rightindex;j++)
        result[i + j] = rightArr[j];
    free(leftArr);
    free(rightArr);
    return result;
}