题目描述
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
题解；
分两个过程：
先用前序遍历+中序遍历恢复二叉树，这个应该都会。。
打印二叉树的后视图，其实就是层序遍历中每一层的最后一个元素
代码；
我的代码不知为何错了，，调不出来了。。
class Solution {
public:
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型vector 先序遍历 * @param zhongxu int整型vector 中序遍历 * @return int整型vector */
vector<int>res;
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
TreeNode* t=rebulid(xianxu,zhongxu,0,0,zhongxu.size()-1);
right(t);
return res;
}
TreeNode* rebulid(vector<int> &pre,vector<int> &in,int root,int l,int r)
{
if(l>r)return NULL;
TreeNode* tree=new TreeNode(pre[root]);
int mid=l;
while(mid<r&&pre[root]!=in[mid])mid++;
tree->left=rebulid(pre, in, root+1, l, mid);
tree->right=rebulid(pre,in,root+1+mid-l,mid+1,r);
return tree;
}
void right(TreeNode *root)
{
queue<TreeNode*>q;
if(!root)return ;
q.push(root);
while(!q.empty())
{
int size=q.size();
res.push_back(q.front()->val);
while(size--)
{
TreeNode* node=q.front();
q.pop();
if(node->right)q.push(node->right);
if(node->left)q.push(node->right);
}
}
}
};
借鉴的某大佬代码：
class Solution {
public:
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型vector 先序遍历 * @param zhongxu int整型vector 中序遍历 * @return int整型vector */
TreeNode* mytree(vector<int> x,vector<int> z)
{
if(x.size()==0||z.size()==0)
return nullptr;
TreeNode* root=new TreeNode(x[0]);
int t=distance(z.begin(),find(z.begin(),z.end(),x[0]));
vector<int> xleft(x.begin()+1,x.begin()+t+1);
vector<int> xright(x.begin()+t+1,x.end());
vector<int> zleft(z.begin(),z.begin()+t);
vector<int> zright(z.begin()+t+1,z.end());
root->left=mytree(xleft,zleft);
root->right=mytree(xright,zright);
return root;
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
TreeNode* root=mytree(xianxu,zhongxu);
vector<int> res;
queue<TreeNode*> que;
if(root==nullptr) return res;
que.push(root);
while(!que.empty())
{
int len=que.size();
for(int i=0;i<len;i++)
{
TreeNode* t=que.front();
que.pop();
if(i==len-1)
res.emplace_back(t->val);
if(t->left) que.push(t->left);
if(t->right) que.push(t->right);
}
}
return res;
}
};
京公网安备 11010502036488号