思路
1、根据前序+中序遍历重建二叉树
2、层序遍历输出二叉树的每一层的最右边的元素
代码
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型vector 先序遍历 * @param zhongxu int整型vector 中序遍历 * @return int整型vector */ // 重建二叉树,核心是找到pre的的第一个元素(root)在in中的index,分为左右子树分别递归 TreeNode* reconstruct(vector<int>& pre, int pre_left, int pre_right, vector<int>& in, int in_left, int in_right){ if(pre_left>pre_right){ return nullptr; } TreeNode* root = new TreeNode(pre[pre_left]); // 先找到pre中的第一个(root)在in中的index int index = in_left; while(index<=in_right && in[index]!=pre[pre_left]){ index++; } int width = index - 1 - in_left; root->left = reconstruct(pre, pre_left+1, pre_left+1+width, in, in_left, index-1); root->right = reconstruct(pre, pre_left+1+width+1, pre_right, in, index+1, in_right); return root; } // 打印二叉树的右视图 vector<int> res; void helper(TreeNode* root){ if(root==nullptr) return; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int len = q.size(); // int i = 1; while(len-- > 0){ auto node = q.front(); q.pop(); if(node->left!=nullptr){ q.push(node->left); } if(node->right!=nullptr){ q.push(node->right); } if(0 == len){ res.push_back(node->val); } } } } vector<int> solve(vector<int>& pre, vector<int>& in) { // write code here auto root = reconstruct(pre, 0, pre.size()-1, in, 0, in.size()-1); helper(root); return res; } };