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

Question

给定一个二叉树的根节点 root ，返回它的 中序 遍历。
要求返回一个序列，这个为什么是返回一个指针呢？

力扣 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

Answer 1

void doInorderTraversal(struct TreeNode* root, int *ret, int* returnSize) {
    if(root) {
        doInorderTraversal(root->left, ret, returnSize);   // (1)
        ret[ (*returnSize)++ ] = root->val;                // (2)
        doInorderTraversal(root->right, ret, returnSize);  // (3)
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret = (int *)malloc(150 * sizeof(int));           // (4)
    *returnSize = 0;                                       // (5)
    doInorderTraversal(root, ret, returnSize);
    return ret;
}

• $(1)$ 递归遍历左子树；
• $(2)$ 中序的核心，将当前树的值塞入结果数组；
• $(3)$ 递归遍历右子树；
• $(4)$ 申请一个数组作为结果数组的缓存；
• $(5)$ 初始化结果数组的长度；