#include <vector>

#include <iostream>

#include <deque>

#include <unordered_map>

using std::vector;

using std::deque;

using std::unordered_map;

/**

* Definition for a binary tree node.

*/

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

if (preorder.size() == 0 || inorder.size() == 0) return nullptr;

for (int i = 0; i < inorder.size(); i++) inorderMap[inorder[i]] = i;

TreeNode *root = generate(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);

return root;

}

private:

unordered_map<int, int> inorderMap;

TreeNode* generate(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie) {

if (ps > pe) return nullptr;

// int i = 0;

// for (i = is; i <= ie; i++) if (preorder[ps] == inorder[i]) break;

int i = inorderMap[preorder[ps]];

int leftCount = i - is;

TreeNode* node = new TreeNode(preorder[ps]);

node->left = generate(preorder, ps+1, ps+leftCount, inorder, is, i-1);

node->right = generate(preorder, ps+leftCount+1, pe, inorder, i+1, ie);

return node;

}

};

void bfs(TreeNode* root) {

if (!root) return;

deque<TreeNode*> queue;

queue.push_back(root);

while(!queue.empty()) {

TreeNode* node = queue.front();

queue.pop_front();

std::cout << node->val << " ";

if (node->left) queue.push_back(node->left);

if (node->right) queue.push_back(node->right);

}

std::cout << std::endl;

}

void levelorder(TreeNode* root) {

if (!root) return;

bfs(root);

}

int main(int argc, char const *argv[])

{

vector<int> preorder{3, 9, 20, 15, 7};

vector<int> inorder{9, 3, 15, 20, 7};

Solution s;

TreeNode* root = s.buildTree(preorder, inorder);

levelorder(root);

return 0;

}