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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) {val = x; left = nullptr; right = nullptr;}
    };

    TreeNode* bulidTree(vector<int>& pre, vector<int>& mid, int l1, int r1, int l2, int r2) {
        if(l1 > r1 || l2 > r2)
            return nullptr;
        TreeNode* root = new TreeNode(pre[l1]); // 前序数组中的第一个数就是根节点
        for(int i = l2; i <= r2; i++){
            if(root->val == mid[i]) { 
                // 查找中序数组中和根节点值相同的元素，其前面的元素为左子树，后面元素为右子树
                root->left = bulidTree(pre, mid, l1 + 1, l1 + i - l2, l2, i - 1);
                root->right = bulidTree(pre, mid, l1 + i - l2 + 1, r1, i + 1, r2);
            }
        }
        return root;
    }

    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        TreeNode* root = bulidTree(xianxu, zhongxu, 0, xianxu.size() - 1, 0, zhongxu.size() - 1);
        vector<int> res;
        if(root == nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int len = q.size(); // 统计现在一层的节点数量，当节点数到达最后一个时，将节点值存入数组res
            for(int i = 0; i < len; i++) {
                auto t = q.front();
                if(i == len - 1)
                    res.push_back(t->val);
                q.pop();
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
        }
        return res;
    }

};