94. 二叉树的中序遍历

先写一个用递归实现比较简单的C语言版本的，虽然这个版本还有问题！！！

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

示例:

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

输出: [1,3,2]

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

C语言要动态分配数组内存，比C++的vector<int>稍微麻烦一些

而且vector直接push_back就好了，可是C的数组还得下标赋值！！！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int num = getNum(root);
    returnSize = (int*)malloc(num*sizeof(int));//为了返回数组动态分配内存
    int index = 0;
    traverse(root, returnSize, &index);
    for(int i = 0; i < num; i++){
        printf("returnSize[%d] = %d\n", i, returnSize[i]);
    }
    return returnSize;
}
int getNum(struct TreeNode*root){
    //获取节点个数
    if(root == NULL)     return 0;
    else return getNum(root->left) + getNum(root->right) + 1;
}
void traverse(struct TreeNode* root, int *returnSize, int*index){
    //index作为当下数组赋值的下标的地址
    if(root == NULL)    return;
    else{
        traverse(root->left, returnSize, index);
        returnSize[(*index)] = root->val;
        (*index) += 1;
        traverse(root->right, returnSize, index);
    }
}

结果在LeetCode上运行的结果是这样的，但是调试信息显示数组元素已经正常赋值了，而且我也是动态分配内存的，

不是特别懂为什么实际返回的是一个空数组！！！？？？

欢迎大家评论和提出意见！！！

用栈实现中序访问的代码如下！！！

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> returnArray;
        stack<struct TreeNode*> nodeStack;//栈的元素是指针，而不是相应结构体
        struct TreeNode* p = root;
        while(p != NULL || !nodeStack.empty()){
            if(p){
                nodeStack.push(p);
                p = p->left;
            }
            else if(!nodeStack.empty()){
                //此时nodeStack.top()就是一个没有左子节点的节点，所以直接入数组，遍历顺序是：左中右
                returnArray.push_back(nodeStack.top()->val);
                p = nodeStack.top()->right;
                nodeStack.pop();
            }
            
        }
        return returnArray;
    }
};

参考blog：https://blog.csdn.net/hengyishu/article/details/47204895

莫里斯解法(morris traversal)的原理没怎么看懂，还在学习~~~