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

#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        if (preOrder.empty() || vinOrder.empty())
            return NULL;
        TreeNode* root = new TreeNode(preOrder[0]);
        int i;
        for (i = 0; i < vinOrder.size(); i++) {
            if (vinOrder[i] == preOrder[0]) {

                break;
            }

        }
        vector<int> preLeft(preOrder.begin() + 1, preOrder.begin() + i + 1);
        vector<int> preRight(preOrder.begin() + i + 1, preOrder.end());
        vector<int> midLeft(vinOrder.begin(), vinOrder.begin() + i);
        vector<int> midRight(vinOrder.begin() + i + 1, vinOrder.end());
        root->left = reConstructBinaryTree(preLeft, midLeft);
        root->right = reConstructBinaryTree(preRight, midRight);

        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        TreeNode* root = reConstructBinaryTree(preOrder, inOrder);
        queue<TreeNode*> que;
        que.push(root);
        vector<int> res;
        while (!que.empty()) {
            int levelSize = que.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* tmp = que.front();
                que.pop();
                if (i == levelSize - 1) {
                    res.push_back(tmp->val);
                }
                if (tmp->left) que.push(tmp->left);
                if (tmp->right) que.push(tmp->right);
            }
        }
        return res;
    }

};