二叉树的前序中序后序遍历—采用递归与迭代两种方法实现嗷

二叉树的前序/中序/后序遍历—采用递归与迭代两种方法实现嗷 二叉树的前序/中序/后序遍历—采用递归与迭代两种方法实现（以leetcode二叉树遍历为例题） 前序遍历

递归算法

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int * returns = (int *)malloc(sizeof(int)* 110);
    preorder(root,returns,returnSize);
    return returns;
}
void preorder(struct TreeNode* root,int returns[],int *returnSize)
{
    if(root == NULL)
    {   
        return;
    }
    // printf("%d",root->val);
    // preorder(root,returns,&returnSize);
    returns[*returnSize] = root->val;
    (*returnSize)++;
    preorder(root->left,returns,returnSize);
    preorder(root->right,returns,returnSize);
    
}

迭代
这里比较详细（复杂）的写出来，包括栈的存储方式定义，入栈，出栈，判空以及初始化方法，下面中序与后序遍历时进行了优化！减少了多个方法函数！
::重点记忆后边的写法::

typedef struct stack{
    struct TreeNode* data[110];
    int top;
}stack;
void push(stack *s,struct TreeNode *x)
{
    s->data[(s->top)] = x;
    (s->top)++;
}
struct TreeNode *pop(stack *s,struct TreeNode *x)
{
    x = s->data[--(s->top)];
    // printf("%d",x->val);
    
    return x;
}
void init(stack *s)
{
    (s->top) = 0;
}
int empty(stack s)
{
    if(s.top == 0)
        return 0;
    return 1;
}
void visit(struct TreeNode* x,int returns[],int *returnSize)
{
    returns[(*returnSize)++] = x->val;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* returns = (int *)malloc(sizeof(int)* 110);
    struct TreeNode *m;
    m = root;
    stack s;
    init(&s);
    while(m != NULL || empty(s)!= 0)
    {
        if(m)
        {
            visit(m,returns,returnSize);
            push(&s,m);
            // printf("s%ds",m->val);
            m = m->left;
        }
        else
        {
            m = pop(&s,m);
            m = m->right;
        }
    }
    return returns;
}

中序遍历

递归算法

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *returns = (int *)malloc(sizeof(int )* 110);
    inorder(root,returns,returnSize);
    return returns;
}
void inorder(struct TreeNode* root,int returns[],int *returnSize)
{
    if(root == NULL)
        return;
    inorder(root->left,returns,returnSize);
    returns[(*returnSize)++] = root->val;
    inorder(root->right,returns,returnSize);
}

迭代
我们也可以用迭代的方式实现递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，代码附下。

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* returns = (int *)malloc(sizeof(int )*110);
    struct TreeNode *s[110];
    int top = 0;
    struct TreeNode *m = root;
    while(m!=NULL || top != 0)
    {
        if(m)
        {
            s[top++] = m;
            m = m->left;
        }
        else
        {
            m = s[--top];
            returns[(*returnSize)++] = m->val;
            
            m = m -> right;
        }
    }
    return returns;
}

后序遍历

递归

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *returns = (int *)malloc(sizeof(int)* 110);
    postorder(root,returns,returnSize);
    return returns;
}
void postorder(struct TreeNode* root,int returns[],int *returnSize)
{
    if(root == NULL)
    {
        return;
    }
    postorder(root->left,returns,returnSize);
    postorder(root->right,returns,returnSize);
    returns[(*returnSize)++] = root->val;
}

迭代 （卡了一会儿）

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *returns = (int *)malloc(sizeof(int)* 110);
    struct TreeNode* data[110];
    int top = 0;
    struct TreeNode* m = root;
    struct TreeNode* pre = NULL;
    while(m || top != 0)
    {
        while(m)
        {
            pre = m;
            data[top++] = m;
            m = m->left;
        }
        m = data[--top]; //当前m为空，肯定要m找到上一个结点，才能判断
        if(m->right != NULL && m->right != pre) //下面还有子结点
        {
            data[top++] = m;
            m = m->right;
        }
        else
        {
            pre = m;  //pre记录现在的结点 当m->right与pre相等时可以记录当前结点
            returns[(*returnSize)++] = pre->val;
            m = NULL; //m去栈里找栈顶元素
        }   
    }
    return returns;
}