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

class Solution {
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        TreeNode* root = reBuildBST(xianxu, zhongxu);
        vector<int> res;

        // 层序遍历收集二叉树的右视图的节点的值
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            TreeNode* node = nullptr;
            while(size--) {
                node = que.front(); que.pop();
                if(node->left)    que.push(node->left);
                if(node->right)    que.push(node->right);
            }
            if(node)
                res.push_back(node->val);
        }
         return res;
    }

    // 重建二叉树
    TreeNode* reBuildBST(vector<int>& xianxu, vector<int>& zhongxu) {
        if(xianxu.size()==0 || zhongxu.size()==0)
            return nullptr;

        int rootVal = xianxu[0];
        TreeNode* root = new TreeNode(rootVal);

        int index = 0;
        while(index < zhongxu.size()) {
            if(zhongxu[index] == rootVal)
                break;
            index ++;
        }

        vector<int> lzhongxu(zhongxu.begin(), zhongxu.begin()+index);
        vector<int> rzhongxu(zhongxu.begin()+index+1, zhongxu.end());

        vector<int> lxianxu(xianxu.begin()+1, xianxu.begin()+1+index);
        vector<int> rxianxu(xianxu.begin()+1+index, xianxu.end());

        root->left = reBuildBST(lxianxu, lzhongxu);
        root->right = reBuildBST(rxianxu, rzhongxu);

        return root;
    }
};