LeetCode 94. 二叉树的中序遍历（C语言）

题目描述

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

示例:

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

递归：

void inorder(struct TreeNode* root, int* returnSize, int *ans){
    if(root){
        inorder(root->left,returnSize,ans);
        ans[(*returnSize)++]=root->val;
        inorder(root->right,returnSize,ans);
    }
}    
int TreeSize(struct TreeNode* root){
    if(!root)
        return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *ans=(int*) malloc(sizeof(int)*TreeSize(root));
    *returnSize=0;
    inorder(root, returnSize, ans);
    return ans;
}

非递归：

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    struct TreeNode** stack=(struct TreeNode**)malloc((sizeof(struct TreeNode*)*100));
    int* ans=(int*)malloc(sizeof(int)*100);
    int i=0;
    *returnSize=0;
    while(i||root){
        if(root){
            stack[i++]=root;
            root=root->left;
        }
        else{
            root=stack[--i];
            ans[(*returnSize)++]=root->val;
            root=root->right;
        }
    }
    return ans;    
}