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

#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* buildTree(vector<int>& pre, vector<int>& vin) {
        int pre_size = pre.size();
        int vin_size = vin.size();

        if (pre_size == 0 || vin_size == 0)
            return nullptr;

        TreeNode* root = new TreeNode(pre[0]);

        for (int i = 0; i < vin_size; i++) {
            if (pre[0] == vin[i]) {

                //左子树先序
                vector<int > leftpre(pre.begin() + 1, pre.begin() + 1 + i);
                //左子树中序
                vector<int > leftvin(vin.begin(), vin.begin() + i);
                //左孩子
                root->left = buildTree(leftpre, leftvin);
                //右子树先序
                vector<int > rightpre(pre.begin() + i + 1, pre.end());
                //右子树先序
                vector<int > rightvin(vin.begin() + i + 1, vin.end());
                //右孩子
                root->right = buildTree(rightpre, rightvin);
                break;
            }
        }
        return root;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here

        TreeNode* root = buildTree(xianxu, zhongxu);
        vector<int > rightview = {};

        if (xianxu.size() == 0 || zhongxu.size() == 0) {
            return rightview;
        }

        queue<TreeNode *> qu;
        qu.push(root);
        bool isRight = true;
        while (!qu.empty()) {
            int size = qu.size();
            isRight = true;
            while (size--) {
                TreeNode* node = qu.front();
                qu.pop();
                if (isRight) {
                    rightview.push_back(node->val);
                    isRight = false;
                }

                if (node->right) {
                    qu.push(node->right);
                }
                if (node->left) {
                    qu.push(node->left);
                }
            }
        }

        return rightview;


    }
};