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

class Solution {
    unordered_map<int, int> hash;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        for (int i = 0; i < zhongxu.size(); i++) hash[zhongxu[i]] = i;
        auto root = build(xianxu, zhongxu, 0, 0, zhongxu.size() - 1);
        
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int len = q.size();
            for (int i = 0; i < len; i++) {
                auto t = q.front();
                q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
                if (i == len - 1) res.push_back(t->val);
            }
        }

        return res;
    }

    TreeNode* build(vector<int>& pre, vector<int>& vin, int proot, int il, int ir) {
        if (il > ir) return nullptr;
        int iroot = hash[pre[proot]];
        auto root = new TreeNode(pre[proot]);
        root->left = build(pre, vin, proot + 1, il, iroot - 1);
        root->right = build(pre, vin, proot + (iroot - il) + 1, iroot + 1, ir);
        return root;
    } 
};

• 思路：二叉树的层序遍历
• 1、按照上一题的思路重建二叉树
• 2、层序遍历，保存每一层的最后一个节点
• 时间复杂度：O(n)
• 空间复杂度：O(n)