leetcode-0094

题目：

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

注意事项：

1.输入树为空时，返回长度指针不为空，需置返回长度为0。

可利用代码模板：

1.栈（MyStackType）
2.获取树结点数函数（GetTreeSize)

#include <stdio.h>

#define MY_DEBUG printf
// #define MY_DEBUG
#define  MLOGD     MY_DEBUG
#define MLOGI       MY_DEBUG
#define MLOGE      MY_DEBUG

typedef struct {
    int *buf;
    int top;
    int size;
} MyStackType;

static MyStackType g_stack = {
    .buf = NULL,
    .top = 0,
    .size = 0
};

int StackPush(int val)
{
    if (g_stack.top >= g_stack.size) {
        MLOGE("\n");
        return -1;
    }
    MLOGI("---------------------push %d\n", val);
    g_stack.buf[g_stack.top++] = val;
    return 0;
}

int StackPop(void)
{
    if (g_stack.top <= 0) {
        MLOGE("\n");
        return -1;
    }

    return g_stack.buf[--g_stack.top];
}

int StackInit(int size)
{
    if (size <= 0) {
        return -1;
    }
    g_stack.buf = (int *)malloc(size * sizeof(int));
    if (g_stack.buf == NULL) {
        return -1;
    }
    g_stack.size = size;
    g_stack.top = 0;
    return 0;
}

void StackDeInit(void)
{
    if (g_stack.buf != NULL) {
        free(g_stack.buf);
        g_stack.buf = NULL;
    }
    g_stack.size = 0;
    g_stack.top = -1;
}

int RebuildTree(struct TreeNode *node)
{
    if (node == NULL) {
        MLOGE("\n");
        return -1;
    }
    int ret = 0;
    MLOGI("val=%d, node->left=%p\n", node->val, node->left);

    if (node->left != NULL) {
        ret += RebuildTree(node->left);
    }
    ret += 1;
    StackPush(node->val);
    MLOGI("val=%d, node->right=%p\n", node->val, node->right);
    if (node->right != NULL) {
        ret += RebuildTree(node->right);
    }
    return ret;
}

int GetTreeSize(struct TreeNode *root)
{
    struct TreeNode *node = root;
    if (node == NULL) {
        return 0;
    }
    int count = 1 + GetTreeSize(root->left) + GetTreeSize(root->right);

    return count;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    MLOGI("root=%p\n", root);
    if ((root == NULL) || (returnSize == NULL)) {
        if (returnSize != NULL) {
            *returnSize = 0;
        }
        return NULL;
    }
    int count = GetTreeSize(root);
    if (count <= 0) {
        *returnSize = 0;
        return NULL;
    }
    int ret = StackInit(count);
    if (ret < 0) {
        return NULL;
    }
    MLOGI("count=%d\n", count);
    ret = RebuildTree(root);
    *returnSize = g_stack.top;
    MLOGI("returnSize=%d, ret=%d\n", *returnSize, ret);
    return g_stack.buf;
}