【二叉树】前序中序后序遍历统一！

思路：三种遍历统一实现

1.先将根结点入栈

2.当栈中仍有元素时遍历：

取出栈中元素。判断是否为NULL

1.如果不为NULL：如果其有左右孩子，先入栈右孩子，之后入栈自身，再在后面加上标签NULL表示此结点还未被访问过。再入栈左孩子

2.如果为NULL，取出NULL之前一位元素，放入ret数组中

中序遍历：

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);

    if(!root)
        return ret;
    
    struct TreeNode* stack[150];
    int stack_top = 0;

    stack[stack_top++] = root;

    while(stack_top) {
        struct TreeNode* temp = stack[--stack_top];
        if(temp != NULL) {
            if(temp->right)
                stack[stack_top++] = temp->right;
            stack[stack_top++] = temp;
            stack[stack_top++] = NULL;
            if(temp->left)
                stack[stack_top++] = temp->left;
        } else {
            ret[(*returnSize)++] = stack[--stack_top]->val;
        }
    }
    return ret;
}

前序遍历：

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);

    if(!root)
        return ret;
    
    struct TreeNode* stack[150];
    int stack_top = 0;

    stack[stack_top++] = root;

    while(stack_top) {
        struct TreeNode* temp = stack[--stack_top];
        if(temp != NULL) {
            if(temp->right)
                stack[stack_top++] = temp->right;
            if(temp->left)
                stack[stack_top++] = temp->left;
						stack[stack_top++] = temp;
            stack[stack_top++] = NULL;
        } else {
            ret[(*returnSize)++] = stack[--stack_top]->val;
        }
    }
    return ret;
}

后序遍历：

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* ret = (int*)malloc(sizeof(int) * 100);

    if(!root)
        return ret;
    
    struct TreeNode* stack[150];
    int stack_top = 0;

    stack[stack_top++] = root;

    while(stack_top) {
        struct TreeNode* temp = stack[--stack_top];
        if(temp != NULL) {
						stack[stack_top++] = temp;
            stack[stack_top++] = NULL;
            if(temp->right)
                stack[stack_top++] = temp->right;
            if(temp->left)
                stack[stack_top++] = temp->left;
        } else {
            ret[(*returnSize)++] = stack[--stack_top]->val;
        }
    }
    return ret;
}