题解 | #输出二叉树的右视图#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        int n = preOrder.size();
        int m = vinOrder.size();
        if (n == 0 || m == 0)
            return nullptr;
        TreeNode* root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.size(); i++)
            if (preOrder[0] == vinOrder[i]) {
                vector<int> lpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
                vector<int> lvin(vinOrder.begin(), vinOrder.begin() + i);
                root->left = reConstructBinaryTree(lpre, lvin);

                vector<int> rpre(preOrder.begin() + i + 1, preOrder.end());
                vector<int> rvin(vinOrder.begin() + i + 1, vinOrder.end());
                root->right = reConstructBinaryTree(rpre, rvin);

                break;
            }
        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        TreeNode* root=reConstructBinaryTree(preOrder, inOrder);
        vector<int> res;
        if(root==nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int length=q.size();
            for(int i=0;i<length;i++)
            {
                TreeNode* temp=q.front();
                q.pop();
                if(i==length-1)
                    res.push_back(temp->val);
                if(temp->left!=nullptr)
                    q.push(temp->left);
                if(temp->right!=nullptr)
                    q.push(temp->right);
            }
        }
        return res;
    }
};