首页 > 试题广场 >

输出二叉树的右视图

[编程题]输出二叉树的右视图
  • 热度指数：56459 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

数据范围：
要求： 空间复杂度 ，时间复杂度

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

所以对应的输出为[1,3,5]。
示例1

输入

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

输出

[1,3,5]

备注:
二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。
算法知识视频讲解
添加回答
C
牛客448830658号头像 牛客448830658号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param preOrderLen int preOrder数组长度
 * @param inOrder int整型一维数组 中序遍历
 * @param inOrderLen int inOrder数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int *res;
int cnt=0;
void p(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen )
{   if(preOrderLen==0) return;
    int i=0;
    int cnt_copy=cnt;
    
    res[cnt++]=preOrder[0];
    while(inOrder[i]!=preOrder[0])
    {
        i++;
    }
    p(preOrder+1,i,inOrder,i);
    cnt=cnt_copy+1;
    p(preOrder+i+1,preOrderLen-1-i,inOrder+i+1,inOrderLen-1-i);
    
}
int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    res=(int *)malloc(sizeof(int)*preOrderLen);
    p(preOrder,preOrderLen,inOrder,inOrderLen);
    cnt=0;
    while(res[cnt]!=0){
        cnt++;
    }
    *returnSize=cnt;
    return res;
}
代码很丑，但是排名不低。这样做就是先遍历节点，并让节点在合适处赋值。由于先左后右的顺序，如果该层在右边有节点，就会因为函数递归至此覆盖了左边的节点值；若没有，则就是该节点，符合右视图的预期。
发表于 2024-09-03 14:19:59 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int searchArr(int *Arr, int ArrLen, int p) {
    int i;
    for(i=0;i<ArrLen;i++) {
        if(p==Arr[i])
            return i;
    }
    return -1;
}

void presolve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* Return, int* returnSize ) {
    int *Lres, *Rres, LresLen, RresLen, i;
    if(!preOrderLen) {
        (*returnSize) = 0;
        return;
    }
    Lres = (int*)malloc(100000);
    Rres = (int*)malloc(100000);
    
    {
        int leftTreeLen, rightTreeLen;
        leftTreeLen = searchArr(inOrder, inOrderLen, preOrder[0]);
        rightTreeLen = preOrderLen-1-leftTreeLen;
        presolve(preOrder+1, leftTreeLen, inOrder, leftTreeLen, Lres, &LresLen);
        presolve(preOrder+1+leftTreeLen, rightTreeLen, inOrder+leftTreeLen+1, rightTreeLen, Rres, &RresLen);
    }

    Return[0]=preOrder[0];
    for(i=0;i<(LresLen>RresLen? LresLen : RresLen);i++) {
        if(Rres[i])
            Return[1+i] = Rres[i];
        else
            Return[1+i] = Lres[i]; 
    }
    (*returnSize) = (LresLen>RresLen? LresLen : RresLen)+1;

    return;
}
int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    int *res;
    res = (int*)malloc(100000);
    memset((unsigned char*)res,0,100000);
    presolve(preOrder, preOrderLen, inOrder, inOrderLen, res, returnSize );
    return res;
}

编辑于 2024-03-17 16:45:31 回复(0)
C
牛客218521332号头像 牛客218521332号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param preOrderLen int preOrder数组长度
 * @param inOrder int整型一维数组 中序遍历
 * @param inOrderLen int inOrder数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

#include <stdlib.h>
void constructBinaryTree(int* preOrder, int preOrderLen, int *inOrder, int inOrderLen, int* result, int* returnSize, int level) {
    if (preOrderLen == 0) {
        return;
    }
    int rootValue = preOrder[0];
    result[level] = rootValue;
    int index = 0;
    while (inOrder[index] != rootValue) {
        index ++;
    }
    constructBinaryTree(preOrder + 1, index, inOrder, index, result, returnSize, level + 1);
    constructBinaryTree(preOrder + 1 + index, preOrderLen - index - 1, inOrder + index + 1, inOrderLen - index - 1, result, returnSize, level + 1);
    if (level + 1 > *returnSize) {
        *returnSize = level + 1;
    }
}

int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    // write code here
    *returnSize = 0;
    int* result = (int*)malloc(sizeof(int) * 1000);
    constructBinaryTree(preOrder, preOrderLen, inOrder, inOrderLen, result, returnSize, 0);
    return result;
}

编辑于 2024-01-03 23:05:07 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
static struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen )
{
    // write code here
    struct TreeNode*root=NULL;
    if(preOrderLen&&vinOrderLen)
    {
        root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val=*preOrder;
        root->left=NULL;
        root->right=NULL;
        struct TreeNode*left=NULL;
        struct TreeNode*right=NULL;
        int i=0;
        while(*(vinOrder+i)!=*preOrder)
        {
            i++;
        }
        i++;
        left=reConstructBinaryTree(preOrder+1,i-1,vinOrder,i-1);
        right=reConstructBinaryTree(preOrder+i,vinOrderLen-i,vinOrder+i,vinOrderLen-i);
        root->left=left;
        root->right=right;
    }

    return root;
}

int* solve(int* preOrder, int preOrderLen, int* inOrder, int inOrderLen, int* returnSize ) {
    // write code here
    struct TreeNode* root=reConstructBinaryTree(preOrder, preOrderLen, inOrder,inOrderLen) ;
    struct TreeNode*T[1000];
    int front=0;
    int rear=0;
    int *arr=(int*)malloc(sizeof(int));
   
    if(root)
    {
        T[0]=root;
        front++;
        *returnSize=0;
        while(front!=rear)
        {  
            T[front]=NULL;
            front=(++front)%1000;
            *(arr+(*returnSize))=T[rear]->val;
            ++(*returnSize);
            while(T[rear])
            {
                if(T[rear]->right)
                {
                    T[front]=T[rear]->right;
                    front=(++front)%1000;
                }
                if(T[rear]->left)
                {
                    T[front]=T[rear]->left;
                    front=(++front)%1000;
                }
                rear=(++rear)%1000;
            }
            rear=(++rear)%1000;
        }
    }
    return arr;

发表于 2023-06-30 20:16:56 回复(0)
C
碧秋头像 碧秋
C语言，递归重建树，二叉树层次遍历。因为C中没有queue，所以使用数组模拟循环队列；没有vector的动态结构，所以使用malloc和realloc进行动态数组的维护。 
 #define MAXQSIZE 32

typedef struct TreeNode TreeNode;

TreeNode *createByPreIn(int *pre,int prel,int prer,int *in,int inl,int inr){
	if(prel>prer)
		return NULL;
	TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
	root->val=pre[prel];//根据先序中的第一个节点就是根节点
	int k;
	for(k=inl;k<=inr;k++){//根据先序第一个节点找到中序中的根
		if(pre[prel]==in[k])
			break;
	}
	int numl=k-inl;//numl为左子树节点数
	root->left=createByPreIn(pre,prel+1,prel+numl,in,inl,k-1);
	root->right=createByPreIn(pre,prel+numl+1,prer,in,k+1,inr);
	return root;
}
int* rightSideView(struct TreeNode* root, int* returnSize){
    *returnSize=0;
    if(root==NULL)
        return NULL;
	int *res=(int *)malloc(sizeof(int));
	TreeNode* queue[MAXQSIZE];
	int rear=0,front=0;
	queue[rear]=root;//根节点入队
	rear=(rear+1)%MAXQSIZE;
	int size,p=0;
	TreeNode* node=NULL;
	while(front!=rear){//队不空
		size=(rear-front+MAXQSIZE)%MAXQSIZE;
		(*returnSize)++;//++的优先级优于指针*
		res=(int *)realloc(res,sizeof(int)*(*returnSize));//每一层增加一个空间
		while(size>0){//!!!size--最好不要放在这里
			node=queue[front];//出队
			front=(front+1)%MAXQSIZE;

			if(size==1)//当前层最右结点
				res[p++]=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
	}//while
	return res;
}
int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
    TreeNode* root=createByPreIn(xianxu,0,xianxuLen-1,zhongxu,0,zhongxuLen-1);
    return rightSideView(root,returnSize);
}



发表于 2023-03-09 19:19:16 回复(0)
C
牛客213438852号头像 牛客213438852号
先构造，在层序遍历保存最后一个 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param xianxuLen int xianxu数组长度
 * @param zhongxu int整型一维数组 中序遍历
 * @param zhongxuLen int zhongxu数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
struct TreeNode *build(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen){
    if(xianxuLen<=0||zhongxuLen<=0 ) return NULL;
    struct TreeNode *root=(struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val=xianxu[0];
    int i;
    for(i=0;i<zhongxuLen;i++)
        if(zhongxu[i]==xianxu[0]) break;
    root->left=build(&xianxu[1],i,zhongxu,i);
    root->right=build(&xianxu[i+1],xianxuLen-i-1,&zhongxu[i+1],zhongxuLen-i-1);
    return root;
}
int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
    // write code here
    int *a=(int *)malloc(sizeof(int)*(xianxuLen+1));
    *returnSize=0;
    if(xianxu==NULL||xianxuLen<=0||zhongxu==NULL||zhongxuLen<=0) return a;
    struct TreeNode *root=build(xianxu,xianxuLen,zhongxu,zhongxuLen);
    struct TreeNode **q=(struct TreeNode **)malloc(sizeof(struct TreeNode *)*xianxuLen);
    int head=0,tail=0;
    q[tail++]=root;
    while(tail>head){
        struct TreeNode *tem;
        int len=tail-head;
        for(int i=0;i<len;i++){
            tem=q[head++];
            if(tem->left!=NULL) q[tail++]=tem->left;
            if(tem->right!=NULL) q[tail++]=tem->right;
        }
        a[(*returnSize)++]=tem->val;
    }
    return a;
}


发表于 2021-09-27 20:37:11 回复(2)
提交观点

问题信息

树
难度：
10条回答 9541浏览

热门推荐

通过挑战的用户

查看代码

相关试题

输出二叉树的右视图

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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