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 = 0;
  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->left = help(pre,st,mid-1);
  20. 	root->right = help(pre,mid+1,end);
  21. 	return root;
  22. }
  23. TreeNode* bt(vector<int>&pre,vector<int>&in){
  24. 	for(int i = 0;i<in.size();i++){
  25. 		mp[in[i]] = i;
  26. 	}
  27. 	return help(pre,0,in.size()-1);
  28. }
  29. TreeNode* buildTree(){
  30. 	int x;cin>>x;
  31. 	if(x==-1)return nullptr;
  32. 	TreeNode*  root = new TreeNode(x);
  33.  
  34. 	queue<TreeNode*>q;
  35. 	q.push(root);
  36.  
  37. 	while(!q.empty()){
  38. 		auto u = q.front();
  39. 		q.pop();
  40.  
  41. 		if(cin>>x && x!=-1){
  42. 			u->left = new TreeNode(x);
  43. 			q.push(u->left);
  44. 		}
  45.  
  46. 		if(cin>>x && x!=-1){
  47. 			u->right = new TreeNode(x);
  48. 			q.push(u->right);
  49. 		}
  50.  
  51. 	}
  52. 	return root;
  53. }
  54. void preO(TreeNode* root){
  55. 	if(!root)return;
  56. 	cout<<root->val<<endl;
  57. 	preO(root->left);
  58. 	preO(root->right);
  59.  
  60. }
  61. void print(TreeNode* root) {
  62.     if (!root) {
  63.         cout << "[]" << endl;
  64.         return;
  65.     }
  66.  
  67.     vector<string> result;
  68.     queue<TreeNode*> q;
  69.     q.push(root);
  70.  
  71.     while (!q.empty()) {
  72.         TreeNode* curr = q.front();
  73.         q.pop();
  74.  
  75.         if (curr) {
  76.             result.push_back(to_string(curr->val));
  77.             // Push children even if they are null
  78.             q.push(curr->left);
  79.             q.push(curr->right);
  80.         } else {
  81.             result.push_back("null");
  82.         }
  83.     }
  84.  
  85.     // Remove all the trailing "null"s from the back of the result
  86.     while (!result.empty() && result.back() == "null") {
  87.         result.pop_back();
  88.     }
  89.  
  90.     // Print the array with brackets and commas
  91.     cout << "[";
  92.     for (int i = 0; i < result.size(); i++) {
  93.         cout << result[i];
  94.         if (i < result.size() - 1) cout << ",";
  95.     }
  96.     cout << "]" << endl;
  97. }
  98. int main() {
  99. //	TreeNode* root  = buildTree();
  100. 	int n;
  101. 	cin>>n;
  102. 	vector<int>pre(n),in(n);
  103.  
  104. 	for(int i = 0;i < n ;i++){
  105. 		cin>>pre[i];
  106. 	}
  107.  
  108. 		for(int i = 0;i < n ;i++){
  109. 		cin>>in[i];
  110. 	}
  111.  
  112. 	TreeNode* Croot = bt(pre,in);
  113. 	preO(Croot);
  114. 	print(Croot);
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
5
3 9 20 15 7
9 3 15 20 7
stdout
copy 
3
9
20
15
7
[3,9,20,null,null,15,7]
https://ideone.com/RSGgqA
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!