fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. 	int val;
  5. 	TreeNode* left;
  6. 	TreeNode* right;
  7.  
  8. 	TreeNode(int val):val(val),left(nullptr),right(nullptr){};
  9. };
  10. int idx;
  11. unordered_map<int,int>mp;
  12. TreeNode* help(vector<int>&pre,int st,int end){
  13.  
  14. 	if(st>end)return nullptr;
  15. 	int rootVal = pre[idx--];
  16. 	int mid = mp[rootVal];
  17.  
  18. 	TreeNode* root = new TreeNode(rootVal);
  19. 	root->right = help(pre,mid+1,end);
  20.     root->left = help(pre,st,mid-1);
  21.  
  22. 	return root;
  23. }
  24. TreeNode* bt(vector<int>&post,vector<int>&in){
  25. 	for(int i = 0;i<in.size();i++){
  26. 		mp[in[i]] = i;
  27. 	}
  28. 	idx = post.size()-1;
  29. 	return help(post,0,in.size()-1);
  30. }
  31.  
  32.  
  33. void print(TreeNode* root) {
  34.     if (!root) {
  35.         cout << "[]" << endl;
  36.         return;
  37.     }
  38.  
  39.     vector<string> result;
  40.     queue<TreeNode*> q;
  41.     q.push(root);
  42.  
  43.     while (!q.empty()) {
  44.         TreeNode* curr = q.front();
  45.         q.pop();
  46.  
  47.         if (curr) {
  48.             result.push_back(to_string(curr->val));
  49.             // Push children even if they are null
  50.             q.push(curr->left);
  51.             q.push(curr->right);
  52.         } else {
  53.             result.push_back("null");
  54.         }
  55.     }
  56.  
  57.     // Remove all the trailing "null"s from the back of the result
  58.     while (!result.empty() && result.back() == "null") {
  59.         result.pop_back();
  60.     }
  61.  
  62.     // Print the array with brackets and commas
  63.     cout << "[";
  64.     for (int i = 0; i < result.size(); i++) {
  65.         cout << result[i];
  66.         if (i < result.size() - 1) cout << ",";
  67.     }
  68.     cout << "]" << endl;
  69. }
  70. int main() {
  71. //	TreeNode* root  = buildTree();
  72. 	int n;
  73. 	cin>>n;
  74. 	vector<int>post(n),in(n);
  75.  
  76. 	for(int i = 0;i < n ;i++){
  77. 		cin>>post[i];
  78. 	}
  79.  
  80. 		for(int i = 0;i < n ;i++){
  81. 		cin>>in[i];
  82. 	}
  83.  
  84. 	TreeNode* Croot = bt(post,in);
  85. //	preO(Croot);
  86. 	print(Croot);
  87. 	return 0;
  88. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5
9 15 7 20 3
9 3 15 20 7
stdout
copy 
[3,9,20,null,null,15,7]
https://ideone.com/yoRzjf
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!