题解 | #二叉树的中序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
typedef struct Stack {
    struct TreeNode* data[1000];
    int size;
} stack;
stack* init_stack() {
    stack* my_stack = (stack*) malloc(sizeof(stack));
    if (my_stack == NULL) {
        return NULL;
    }
    for (int i = 0; i < 1000; i++) {
        my_stack->data[i] = NULL;
    }
    my_stack->size = 0;
    return my_stack;
}
void push_stack(stack* my_stack, struct TreeNode* value) {
    if (my_stack == NULL) {
        return;
    }
    my_stack->data[my_stack->size] = value;
    my_stack->size++;
}
struct TreeNode* pop_stack(stack* my_stack) {
    if (my_stack == NULL || my_stack->size == 0) {
        return NULL;
    }
    struct TreeNode* Front = my_stack->data[my_stack->size - 1];
    my_stack->size--;
    return Front;
}
bool IsEmpty(stack* my_stack) {
    if (my_stack == NULL || my_stack->size == 0) {
        return true;
    }
    return false;
}
void inorder(struct TreeNode* root, int* returnSize, int* returnArry) {
    struct TreeNode* node = root;
    stack* my_stack = init_stack();
    while (true) {
        if (node != NULL) {
            push_stack(my_stack, node);
            node = node->left;
        } else if (IsEmpty(my_stack)) {
            return;
        } else {
            node = pop_stack(my_stack);
            returnArry[(*returnSize)++] = node->val;
            node = node->right;
        }
    }
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // write code here
    if (root == NULL) {
        return NULL;
    }
    *returnSize = 0;
    int* returnArry = malloc(sizeof(int) * 1000);
    inorder(root, returnSize, returnArry);
    return returnArry;
}