[数据结构与算法]力扣94. 二叉树的中序遍历

?中序遍历：A-B-C-D-E-F-G-H-I-J

递归

/**
 * 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().
 */
#define MAXSIZE 1000

void gothrogh (struct TreeNode* root, int *returnSize, int *ret){
// 叶子节点
    if (root->left == NULL && root->right == NULL){
        ret[*returnSize] = root->val;
        (*returnSize)++;
        return;
    }
// 非叶子节点，依次搜索左子树，输出父节点，搜索右子树
    if (root->left != NULL){
        gothrogh(root->left, returnSize, ret);
    }
    ret[*returnSize] = root->val;
    (*returnSize)++;
    if (root->right != NULL){
        gothrogh(root->right, returnSize, ret);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *ret = (int*)calloc(MAXSIZE, sizeof(int));
    if (root == NULL){return NULL;}
    gothrogh(root, returnSize, ret);
    return ret;
}