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

根据先序和中序构建二叉树，然后进行层序遍历，记录每一层的最右边的节点数据，即为右视图。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* reconstruction(vector<int> &pre, int pl, int pr, vector<int> &mid, int ml, int mr) {
        TreeNode* res = new TreeNode(pre[pl]); // 前序遍历第一个为父节点
        int father = ml - 1;
        while (pre[pl] != mid[++father]) {
            // do nothing  //找到中序遍历中父节点的位置
        }
        if (father > ml) { //有左子节点的情况下，左子节点指针指向递归构建的新节点
            res->left = reconstruction(pre, pl + 1, pl + father - ml, mid, ml, father - 1);
        }
        if (father < mr) { //有右子节点的情况下，右子节点指针指向递归构建的新节点
            res->right = reconstruction(pre, pl + father - ml + 1, pr, mid, father + 1, mr);
        }
        return res;
    }

    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        // 层序遍历， 记录每一层的最后一个数据
        vector<int> ans;
        if (xianxu.empty()) return ans;
        TreeNode* tree = reconstruction(xianxu, 0, xianxu.size()-1, zhongxu, 0, zhongxu.size()-1);
        queue<TreeNode*> que;
        que.push(tree);
        while (!que.empty()) {
            int count = que.size();
            while (count--) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                if (!count) ans.push_back(que.front()->val); // 记录每一层最后一个数据
                que.pop();
            }
        }
        return ans;
    }
};