NC136 #输出二叉树的右视图#

先重构二叉树，后层次遍历。

class Solution {
public:
    unordered_map<int, int> index;
    TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right,vector<int>& in, int in_left, int in_right)
    {
        if (pre_left > pre_right)
            return nullptr;
        int root_val = pre[pre_left];
        int in_root = index[root_val];
        TreeNode* root = new TreeNode(root_val);
        int size_left_subtree = in_root - in_left;
        root->left = rebuild(pre, pre_left + 1, pre_left + size_left_subtree, in, in_left, in_root - 1);
        root->right = rebuild(pre, pre_left + size_left_subtree + 1, pre_right, in, in_root + 1, in_right);
        return root;
    }

    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        int n = xianxu.size();
        vector<int> vec;
        if(n == 0) return vec;
        for (int i = 0; i < n; i++)
            index[zhongxu[i]] = i;
        TreeNode* root = rebuild(xianxu, 0, n - 1, zhongxu, 0, n - 1);
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int len = que.size();
            for(int i = 0; i < len; i++)
            {
                if(i == len - 1)
                    vec.push_back(que.front()->val);
                if(que.front()->left != nullptr) que.push(que.front()->left);
                if(que.front()->right != nullptr) que.push(que.front()->right);
                que.pop();
            }
        }
        return vec;
    }
};