leetcode二叉树的四种遍历(迭代)及构造(C语言)

• 前言
• 一、二叉树中序遍历非递归方法
• • 1.1设计思路
  • 1.2代码
• 二、前序遍历方法
• • 2.1设计思路
  • 2.2代码
• 三、后序遍历
• • 3.1设计思路
  • 3.2代码
• 四、层次遍历
• • 4.1设计思路
  • 4.2代码
• 五、二叉树的构造(递归方法)
• • 5.1设计思路
  • 5.2代码

遍历二叉树（非递归）需要每个结点输出一次，而每个元素只进栈或出栈一次，因此写代码的时候可以将输出与进栈或出栈一起考虑。
实现算法时只考虑树的结点如何按顺序进栈出栈。

1. 依次将p左子树入栈，直至p为空指针（初始p指向根节点）
2. 将结点出栈，输出其值，另p指向其右结点，继续重复1

//代码前半部分为参数声明，while为中序遍历实现
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=0;
    if(root==NULL)
        return NULL;
    int* ans=(int*)malloc(sizeof(int)*100);
    struct TreeNode** stk=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
    int top=-1,i=0;
    struct TreeNode* p=root;//p为遍历指针

    while(p!=NULL || top>-1){
        if(p!=NULL){
            stk[++top]=p;//左节点入栈
            p=p->left;
        }
        else{
            ans[i++]=stk[top]->val;//返回左节点值
            *returnSize=i;
            p=stk[top--]->right;//转到右节点重复以上步骤
        }
    }

    return ans;
}

• 时间复杂度O( n )
• 空间复杂度O( n )

1. 依次将p左子树入栈，入栈前输出p结点值，直至p为空
2. 将结点出栈，输出其值，另p指向其右结点，继续重复1

前序遍历与中序遍历区别在于输出值的时机不同

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=0;
    if(root==NULL)
        return NULL;
    int* ans=(int*)malloc(sizeof(int)*100);
    struct TreeNode** stk=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
    int top=-1,i=0;
    struct TreeNode* p=root;//p为遍历指针

    while(p!=NULL || top>-1){
        if(p!=NULL){
            ans[i++]=p->val;//返回左节点值
            *returnSize=i;
            stk[++top]=p;//左节点入栈
            p=p->left;
        }
        else
            p=stk[top--]->right;//转到右节点重复以上步骤
    }

    return ans;
}

• 时间复杂度O( n )
• 空间复杂度O( n )

1. 将p左子树依次入栈，直至p为空(p初始指向根节点)
2. 如果栈顶右节点存在，且不等于pre，令p指向右节点，重复1，2 ;否则栈顶出栈，并输出值，更新pre

后序遍历每个结点要访问两次，如何确定节点右节点是否访问，设置pre指针记录上一个出栈的指针，防止二次入栈

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=0;
    int* ans=(int*)malloc(sizeof(int)*100);
    struct TreeNode** stk=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
    int top=-1,i=0; //count记录访问右节点的个数
    struct TreeNode* pre=root;//p为遍历指针

    while(root!=NULL || top>-1){
        if(root!=NULL){
            stk[++top]=root;
            root=root->left;
        }
        else if(stk[top]->right!=NULL && stk[top]->right!=pre)
            root=stk[top]->right;
        else{
            pre=stk[top--];
            ans[i++]=pre->val;
            *returnSize=i;
        }
    }

    return ans;
}

• 时间复杂度O( n )
• 空间复杂度O( n )

声明一个队列，将根节点入队，不断读队头，将队头结点左孩子、右孩子入队，直至队列为空。

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize=0;
    * returnColumnSizes=NULL;
    
    if(!root)
        return NULL;
        
    struct TreeNode* que[1000];
    que[0]=root;
    int** ans=NULL;
    int f=0,r=1,i=0,prer;//f、r为队列首位指针 n、m记录当前层和下一层的元素个数,i为层数
    
    while(f!=r){
        prer=r;
        ans=realloc(ans, (i+1)*sizeof(int*));//分配层数对应的数组指针
        ans[i]=calloc(r-f,sizeof(int));//确定每层数组长度
        *returnColumnSizes=realloc(*returnColumnSizes, (i+1)*sizeof(int));//分配层数对应的数组长度
        (*returnColumnSizes)[i]=r-f;//第i层列数
        for(int j=0;f
val;
            if(root->left)
                que[r++%1000]=root->left;
            if(root->right)
                que[r++%1000]=root->right;
        }
        i++;//层数加一
    }
    *returnSize=i;
    
    return ans;
}
 
时间复杂度O( n )
空间复杂度O( n )
 
 
五、二叉树的构造(递归方法) 
5.1设计思路 
 
 
    前序序列的访问顺序是 根节点-左节点-右节点
     中序序列访问顺序 左节点-根节点-右节点
     前序和中序序列左子树都在右子树前。
     前序序列第一个元素肯定为根节点，中序序列根节点两边序列分别是左子树和右子树的中序序列。
     通过前序序列确定根节点，中序序列确定根节点的左子树和右子树，对每个子树的序列进行递归即可。
 
 
5.2代码 
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (inorderSize <= 0 || preorderSize <= 0)//返回条件判定
        return NULL;
        
    struct TreeNode* ans = (struct TreeNode*)malloc(sizeof(struct TreeNode));//
    int i = 0;//左子树结点树计数
    
    while (preorder[0] != inorder[i])
        i++;
    ans->val = preorder[0];
    ans->left = buildTree(preorder + 1, preorderSize - 1, inorder, i);//左子树根节点
    ans->right = buildTree(preorder + i + 1, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);
    //左子树结点都在右子树结点前，因此可以确定先序序列右子树根节点起点

    return ans;
}
 
时间复杂度O( n^2 )（因为每次查找根节点O(n)，使用哈希表可降低时间复杂度）
空间复杂度O( n )