输出二叉树的右视图_牛客题霸_牛客网

两个考点：

给出前序和后续遍历的二叉树，构建二叉树

二叉树构建后，输出右视图

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);
}
};