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

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* reConstructBinaryTreeFun(vector<int>& preOrder, vector<int>& vinOrder,
                                       int preBegin, int preEnd, int vinBegin, int vinEnd) {
        if (preOrder.empty() || vinOrder.empty())
            return nullptr;
        auto root = new TreeNode(preOrder[preBegin]);
        if (preBegin == preEnd)
            return root;
        int index = vinBegin;
        while (index != vinEnd + 1 && vinOrder[index] != preOrder[preBegin]) {
            index++;
        }
        if (index == vinBegin) {
            root->right = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1, preEnd,
                                                   vinBegin + 1, vinEnd);
            return root;
        }
        if (index == vinEnd) {
            root->left = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1, preEnd,
                                                  vinBegin, vinEnd - 1);
            return root;
        }
        root->left = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1,
                                              preBegin + index - vinBegin, vinBegin, index - 1);
        root->right = reConstructBinaryTreeFun(preOrder, vinOrder,
                                               preBegin + index - vinBegin + 1, preEnd, index + 1, vinEnd);
        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        TreeNode* root = reConstructBinaryTreeFun(preOrder, inOrder, 0,
                         preOrder.size() - 1, 0,
                         inOrder.size() - 1);
        if (root == nullptr)
            return {};
        list<TreeNode*> li;
        vector<int> result;
        li.push_back(root);
        while (!li.empty()) {
            {
                int size = li.size();
                while (size--) {
                    if (size == 0)
                        result.push_back(li.front()->val);
                    if (li.front()->left)
                        li.push_back(li.front()->left);
                    if (li.front()->right)
                        li.push_back(li.front()->right);
                    li.pop_front();
                }
            }
        }
        return result;
    };
};