刷题——输出二叉树的右视图
输出二叉树的右视图_牛客题霸_牛客网
两个考点：
给出前序和后续遍历的二叉树，构建二叉树
二叉树构建后，输出右视图
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 求二叉树的右视图* @param preOrder int整型vector 先序遍历* @param inOrder int整型vector 中序遍历* @return int整型vector*/
TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2)
{if(l1>r1 || l2 > r2) return NULL;TreeNode* root = new TreeNode(xianxu[l1]);int rootIndex = 0;for(int i = l2; i<=r2; i++){if(zhongxu[i] == xianxu[l1]){rootIndex = i;break;}}int leftsize = rootIndex - l2;int rightsize = r2 - rootIndex;root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, l2 + leftsize -1);root->right = buildTree(xianxu, r1 - rightsize +1, r1, zhongxu, rootIndex +1, r2);return root;
}vector<int> rightSideView(TreeNode* root)
{vector<int>ans;if(!root) return ans;queue<TreeNode*> q;q.push(root);while(!q.empty()){int cnt = q.size();for(int i= 0; i<cnt; i++){TreeNode* cur = q.front();q.pop();if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);if(i == cnt -1)ans.push_back(cur->val);}}return ans;}vector<int>solve(vector<int>&xianxu, vector<int>& zhongxu)
{vector<int>res;if(xianxu.size() == 0) return res;TreeNode* root = buildTree(xianxu, 0, xianxu.size()-1,zhongxu,0,zhongxu.size()-1);return rightSideView(root);
}
};