二叉树右视图

题目描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

示例1

输入

复制

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

输出

复制

[1,3,5]

 

基本思路：

先构建二叉树

然后层次遍历，记录下每一层的最后一个节点

（或者层次遍历从右往左）

易错点：层次遍历每一层之前先记录下队列大小。

 

struct treenode { int val; treenode* left; treenode* right; treenode(int _val) { val=_val; left=NULL; right=NULL; } }; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型vector 先序遍历 * @param zhongxu int整型vector 中序遍历 * @return int整型vector */ //基于引用+下标范围方式 重构二叉树，减少频繁拷贝带来的开销 treenode* rebulid(vector<int>& x,vector<int>& z,int x_start,int x_end,int z_start,int z_end) { treenode* root=new treenode(x[x_start]); if(x_start==x_end) return root; int len=-1;//找到中序遍历中根节点位置 for(int i=z_start;i<=z_end;i++) if(z[i]==x[x_start]) { len=i; break; } len=len-z_start; if(len>0) //说明root节点有左子树 root->left=rebulid(x,z, x_start+1, x_start+len, z_start,z_start+len-1); if(len<z_end-z_start) //说明root节点有右子树 root->right=rebulid(x,z, x_start+len+1, x_end, z_start+len+1,z_end); return root; } vector<int> right_see(treenode* root) { //每次取层次遍历第一个节点 vector<int> ans; queue<treenode*> q; q.push(root); // cout<<(root->left!=NULL)<<endl; while(q.empty()==false) { // cout<<1<<endl; int len=q.size();//上一层的节点 for(int i=0;i<len-1;i++) //先弹出前面len-1个 { treenode* p=q.front(); q.pop(); if(p->left) q.push(p->left); if(p->right) q.push(p->right); } treenode* p=q.front(); ans.push_back(p->val); //记录最后右边节点 q.pop(); if(p->left) q.push(p->left); if(p->right) q.push(p->right); } return ans; } vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) { // write code here treenode* root=rebulid(xianxu,zhongxu,0,xianxu.size()-1, 0,zhongxu.size()-1); return right_see(root); } };