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

这个方法可能不是最优解，e.....或者说肯定不是最优解🤔
但易于理解
基于重建二叉树和求二叉树的层序遍历，就能完成。

vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) 
    {
        // write code here
        // 构建二叉树
        TreeNode* root = resConstrain(xianxu, zhongxu);

        vector<int> res{}; // 保存层序遍历的结果，这里做一个处理，层序遍历，只保存每层的最后一个数值

        //层序遍历，输出最右边的值
        TreeNode* curr{};
        queue<TreeNode*> queue{};
        queue.push(root);
        while (!queue.empty())
        {
            int n  = queue.size();
            for (int i = 0; i < n; ++i)
            {
                curr = queue.front();
                queue.pop();

                // 注意这里，我们只再每一层的最后一个，才去存进数组
                if (i == n - 1)
                {
                    res.push_back(curr->val);
                }

                if (curr->left)
                {
                    queue.push(curr->left);
                }

                if (curr->right)
                {
                    queue.push(curr->right);
                }
            }
        }
        return res;
    }

    // 重建二叉树，这个和另一道题的解题代码如出一辙，没有任何变化
    TreeNode* resConstrain(vector<int> pre, vector<int> vin)
    {
        int preLen = pre.size();
        int vinLen = vin.size();

        if (preLen == 0 || vinLen == 0)
        {
            return nullptr;
        }

        TreeNode* root = new TreeNode(pre[0]);
        for (int i = 0; i < vinLen; ++i)
        {
            if (pre[0] == vin[i])
            {
                vector<int> preLeft(pre.begin() + 1, pre.begin() + i + 1);
                vector<int> vinLeft(vin.begin(), vin.begin() + i);
                root->left = resConstrain(preLeft, vinLeft);

                vector<int> preRight(pre.begin() + i + 1, pre.end());
                vector<int> vinRight(vin.begin() + i + 1, vin.end());
                root->right = resConstrain(preRight, vinRight);
            }
        }
        return root;
    }