首页 > 试题广场 >

按之字形顺序打印二叉树

[编程题]按之字形顺序打印二叉树
  • 热度指数：537982 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：,树上每个节点的val满足
要求：空间复杂度：，时间复杂度：
例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1

输入

{1,2,3,#,#,4,5}

输出

[[1],[3,2],[4,5]]

说明

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。
示例2

输入

{8,6,10,5,7,9,11}

输出

[[8],[10,6],[5,7,9,11]]
示例3

输入

{1,2,3,4,5}

输出

[[1],[3,2],[4,5]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
hpuer头像 hpuer
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
#include <stdlib.h>
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    *returnSize=0;
    if(NULL==pRoot)
        return NULL;
    struct TreeNode* queue[2000];
    int** res=(int**)malloc(sizeof(int*)*2000);
    *returnColumnSizes=(int*)malloc(sizeof(int)*2000);
    int front=0;
    int rear=0;
    queue[rear]=pRoot;
    rear++;
    while(front!=rear)
    {
        int cur_pos=rear;
        int num=0;
        res[*returnSize]=(int*)malloc(sizeof(int)*(cur_pos-front));
        while(front<cur_pos){
            struct TreeNode* q=queue[front];
            if((*returnSize+1)%2==1)
                res[*returnSize][num++]=q->val;
               
            if((*returnSize+1)%2==0){
                res[*returnSize][cur_pos-front-num-1]=q->val;
                num++;
            }
            if(NULL!=q->left)
            {
                queue[rear]=q->left;
                rear++;
            }
            if(NULL!=q->right)
            {
                queue[rear]=q->right;
                rear++;
            }
            front++;
        }
        (*returnColumnSizes)[*returnSize]=num;
        (*returnSize)++;
    }
    return res;
}
发表于 2023-08-25 16:34:28 回复(2)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes )
{
    // write code here
    int **arr=(int**)malloc(sizeof(int*)*1500);
    *returnColumnSizes=(int*)malloc(sizeof(int*)*1500);
    struct TreeNode*T0[1024];
    struct TreeNode*T1[1024];
    int base0=0;
    int top0=0;
    int base1=0;
    int top1=0;
    int k=0;
    int flag=0;

    if(pRoot)
    {
        flag=1;
        T0[top0]=pRoot;
        top0++;
    }
    while(flag)
    {
        flag=0;
        int j=0;
        *(arr+k)=(int*)malloc(sizeof(int)*pow(2,k));
        if(0==k%2)
        {
            pRoot=T0[--top0];
            while(pRoot)
            {
                arr[k][j]=pRoot->val;/////////
                j++;
                if(pRoot->left)
                {
                    T1[top1++]=pRoot->left;
                    flag=1;
                }
                if(pRoot->right)
                {
                    T1[top1++]=pRoot->right;
                    flag=1;
                }
                if((--top0)<0)
                {
                    break;
                }
                pRoot=T0[top0];
            }
            top0=0;
            *(* returnColumnSizes+k)=j;
            k++;
        }
        else if(1==k%2)
        {
            j=0;
            pRoot=T1[--top1];
            while(pRoot)
            {
                arr[k][j]=pRoot->val;
                j++;
                if(pRoot->right)
                {
                    T0[top0++]=pRoot->right;
                    flag=1;
                }
                if(pRoot->left)
                {
                    T0[top0++]=pRoot->left;
                    flag=1;
                }
                if((--top1)<0)
                {
                    break;
                }
                pRoot=T1[top1];
            }
            *(* returnColumnSizes+k)=j;
            k++;
            top1=0;
        }
    }
    *returnSize=k;
    return arr;
}
发表于 2023-06-26 13:23:52 回复(0)
C
牛客446770844号头像 牛客446770844号 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    *returnSize=0;  //初始化*returnSize=0
    if(pRoot==NULL)  //根节点为空，该树为空树，返回NULL
    return NULL;
    struct TreeNode *queue[1500];//利用队列存放节点
    int **ret=(int**)malloc(sizeof(int*)*1500);//给二维数组分配空间
    *returnColumnSizes=(int*)malloc(sizeof(int)*1500);//给数列列数分配空间
    int rear=0;
    int front=0;//定义队列首尾指针，都初始化为0
    queue[rear++]=pRoot;//将根节点入队
    while(front!=rear){//终止循环条件：队列为空时
        int k=0;//从左往右时数组列数
        int prerear=rear;
        int j=prerear-front-1;//从右往左时的初始下标
        int i=j+1;//从右向左时数组列数
        ret[*returnSize]=(int*)malloc(sizeof(int)*(prerear-front));//给数组第*returnSize行分配（prerear-front）个空间
        while(front<prerear){
            struct TreeNode*p=queue[front];//指针指向队列第一个节点
            if((*returnSize)%2==0)//从0开始，如果该层为偶数层则从左往右输出
            ret[*returnSize][k++]=p->val;

            else
             ret[*returnSize][j--]=p->val;
             //奇数层，从右往左输出
             
            if(p->left!=NULL)
            queue[rear++]=p->left;
            //如果左节点有节点，则存入队列
            if(p->right!=NULL)
            queue[rear++]=p->right;
            //同理，右节点有节点也存入队列
            front++;//当前节点出队
        }
        if((*returnSize)%2==0)
        (*returnColumnSizes)[*returnSize]=k;
        //偶数层，列数=k
        else
        (*returnColumnSizes)[*returnSize]=i;
        //奇数层，列数等于i；
        (*returnSize)++;
        //层数++
    }
    return ret;
}

发表于 2023-06-16 17:10:34 回复(0)
C
我是小安哥头像 我是小安哥
#include <stdlib.h>
int* Result[1500];
struct TreeNode* queue[1500];
int iColumn[1500];

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    *returnSize = 0;
    int iFront = 0;
    int iRear = 0;
    int iLevel = 0;
    int length = 0;

    if (NULL == pRoot) {
        return NULL;
    }

    queue[iRear++] = pRoot;
    while (iFront != iRear) {
        length = iRear - iFront;
        Result[iLevel] = malloc(sizeof(int) * (length));

        for (int i = 0; i < length; i++) {
            struct TreeNode* ptNowNode = queue[iFront++];
            if (iLevel % 2 == 0) { /*从左向右*/
                Result[iLevel][i] = ptNowNode->val;

            } else { /*从右向左*/

                Result[iLevel][length - i - 1] = ptNowNode->val;
            }
            if (ptNowNode->left != NULL) {
                queue[iRear++] = ptNowNode->left;
            }
            if (ptNowNode->right != NULL) {
                queue[iRear++] = ptNowNode->right;
            }
        }
        iColumn[iLevel++] = length;
    }
    *returnSize = iLevel;
    *returnColumnSizes = iColumn;
    return Result;
}
发表于 2023-04-05 17:01:22 回复(0)
C
碧秋头像 碧秋
层序遍历 
#define MAXQSIZE 512

typedef struct TreeNode TreeNode;

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
	*returnSize=0;
    if(pRoot==NULL)return NULL;
	*returnColumnSizes=(int*)malloc(sizeof(int)*100);
	int **res=(int**)malloc(sizeof(int*)*100);
    TreeNode* r=pRoot;
	TreeNode* queue[MAXQSIZE];
	int front=0,rear=0;
	queue[rear]=r;
	rear=(rear+1)%MAXQSIZE;

	int size,level=0,i;
	TreeNode* node;
	while(front!=rear){
		size=(rear-front+MAXQSIZE)%MAXQSIZE;
		(*returnColumnSizes)[level]=size;
		level++;//当前层数，奇数是顺序打印，偶数时从右到左打印
		int* arr=(int*)malloc(sizeof(int)*size);
		i=0;
		while(size>0){
			node=queue[front];
			front=(front+1)%MAXQSIZE;
			if(level%2!=0)
				arr[i++]=node->val;	
			else
				arr[size-1]=node->val;
			if(node->left!=NULL){
				queue[rear]=node->left;
				rear=(rear+1)%MAXQSIZE;
			}
			if(node->right!=NULL){
				queue[rear]=node->right;
				rear=(rear+1)%MAXQSIZE;
			}
			size--;
		}//while size
		res[level-1]=arr;
	}
	*returnSize=level;
	return res;
}


发表于 2023-03-10 16:38:39 回复(0)
C
牛客515960666号头像 牛客515960666号 
//主题思路是在层序遍历基础上，对输出进行修改
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if (!pRoot)
        return NULL;
    int front = 0;
    int rear = 0;
    int preRear = 0;
    int temp = 0;
    int flag = 1;
    struct TreeNode* queue[1500];
    struct TreeNode* p = NULL;
    struct TreeNode* q = NULL;
    int** res = (int**) malloc(sizeof(int*) * 1500);
    *returnSize = 0;
    *returnColumnSizes = (int*) malloc(sizeof(int) * 1500);
    queue[rear++] = pRoot;

    while (rear > front) {
        int k = 0;
        preRear = rear;
        if (flag % 2 == 0)
            temp = rear - 1;
        res[*returnSize] = (int*) malloc(sizeof(int) * (preRear - front));
        while (preRear > front) {
            p = queue[front++];
            if (flag % 2 ==
                    0) {   //若为偶数层，该层队列区间按照从尾到头输出，但是该层的孩子节点进队仍按照
                q = queue[temp--]; //从前到后
                res[*returnSize][k++] = q->val;
            } else
                res[*returnSize][k++] = p->val;
            if (p->left)
                queue[rear++] = p->left;
            if (p->right)
                queue[rear++] = p->right;
        }
        (*returnColumnSizes)[*returnSize] = k;
        *returnSize += 1;
        flag++;
    }
    return res;
}

发表于 2022-10-20 14:52:57 回复(0)
C
牛客323664020号头像 牛客323664020号

哪位大佬帮忙看一下，为啥第19个例子会发生段错误，被折磨了一早上啊😥😥

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* r, int* returnSize, int** returnColumnSizes ) {
    // write code here
    int **ans = (int**)malloc(sizeof(int*)*1502);
    ans[0]=(int*)malloc(sizeof(int));
    ans[1]=(int*)malloc(sizeof(int)*2);
    int *colsize = (int*)malloc(sizeof(int)*1502);
    struct TreeNode *stk[2][1500]={0};
    int top=0, n_top=-1;
    stk[0][0]=r;
    int i=0, cnt=0, left=1;
    while(top!=-1)
    {
        r = stk[0][top--];
        ans[i][cnt++]=r->val;
        if(left)
        {
            if(r->left)
            {
                stk[1][++n_top]=r->left;
            }
            if(r->right)
            {
                stk[1][++n_top]=r->right;
            }
        }
        else
        {
            if(r->right)
            {
                stk[1][++n_top]=r->right;
            }
            if(r->left)
            {
                stk[1][++n_top]=r->left;
            }
        }
        if(top==-1)
        {
            colsize[i]=cnt;
            cnt=0;
            i++;
            memcpy(stk[0],stk[1],sizeof(struct TreeNode*)*1500);
            ans[i+1]=(int*)malloc(sizeof(int)*(n_top*2+2));
            top = n_top;
            n_top=-1;
            left=left?0:1;
        }
    }
    *returnSize = i;
    *returnColumnSizes = colsize;
    return ans;
}
发表于 2022-04-01 14:45:02 回复(0)
C
莫小雨so头像 莫小雨so 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
//利用栈和队列实现
#include<stdlib.h>
static struct TreeNode *queue[1501];
static int head = 0, tail = 0, mid = 0;
static int stack[1501];
static int top;

int** Print(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if(root == NULL) 
    {
        return NULL;
    }
    int **num = (int **)malloc(sizeof(int*) * 1500);
    *returnColumnSizes = (int *)malloc(sizeof(int*) * 1500);
    *returnSize = 0;
    *(queue + (tail ++)) = root;
    mid = 1;
    int flag = 1;
    while(head < tail)
    {
        *(num + (*returnSize)) = (int*)malloc(sizeof(int)*(mid - head));
         (*((*returnColumnSizes) + (*returnSize))) = 0;
        while(head < mid)
        {
            if(flag % 2)
            {
                *(*(num + (*returnSize)) + (*((*returnColumnSizes) + (*returnSize))) ++) = (*(queue +head))->val;
            }
            else
            {
                *(stack + (top ++)) = (*(queue +head))->val;
            }
            if((*(queue + head))->left) *(queue + (tail ++)) = (*(queue + head))->left;
            if((*(queue + head))->right) *(queue + (tail ++)) = (*(queue + head))->right;
            head ++;
        }
        while(top > 0)
        {
            *(*(num + (*returnSize)) + (*((*returnColumnSizes) + (*returnSize))) ++) = *(stack + (--top));
        }
        mid = tail;
        flag ++;
        (*returnSize) ++;
    }
    return num;
}

发表于 2022-03-11 12:48:16 回复(0)
C
小小鼠人可笑可笑头像 小小鼠人可笑可笑
c根本就调不通。
调试下看都是对的，自测就提示错误、输入数据都是一样的。怀疑是调用程序呢没写对。
发表于 2022-01-28 19:23:47 回复(0)
提交观点

问题信息

栈 队列 树
难度：
12条回答 116875浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号