fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. 	TreeNode* left;
  5. 	TreeNode* right;
  6. 	int data;
  7. 	TreeNode(int val):data(val),left(nullptr),right(nullptr){}
  8. };
  9.  vector<vector<int> > treeTraversal(TreeNode* root) {
  10.  	vector<int>pre,post,in;
  11. 	if(root == nullptr)return {in,pre,post};
  12.  
  13.  	stack<pair<TreeNode*,int>>st;
  14.  	st.push({root,1});
  15.  
  16.  	while(!st.empty()){
  17.  	TreeNode* one;
  18. int two;
  19.  	tie(one,two) = st.top();
  20.  		st.pop();
  21.  
  22.  		if(two == 1){
  23.  			st.push({one,2});
  24.  			pre.push_back(one->data);
  25.  		    if(one->left){
  26.  		    	st.push({one->left,1});
  27.  		    }
  28.  		}else if(two == 2){
  29.  			st.push({one,3});
  30.  			in.push_back(one->data);
  31.  			if(one->right){
  32.  				st.push({one->right,1});
  33.  			}
  34.  		}else{
  35.  			post.push_back(one->data);
  36.  		}
  37.  	}
  38.  	return {in,pre,post};
  39.  }
  40.  TreeNode* buildTree(){
  41.  	int x;cin>>x;
  42.  	if(x == -1)return nullptr;
  43.  
  44.  	TreeNode* root = new TreeNode(x);
  45.  
  46.  	queue<TreeNode*>q;
  47.  	q.push(root);
  48.  	while(!q.empty()){
  49.  	 	TreeNode*node =q.front();q.pop();
  50.  	 	cin>>x;
  51.  	 	if(x!=-1){
  52.  	 		node->left = new TreeNode(x);
  53.  	 		q.push(node->left);
  54.  	 	}
  55.  	 	cin>>x;
  56.  	 	if(x!=-1){
  57.  	 		node->right = new TreeNode(x);
  58.  	 		q.push(node->right);
  59.  	 	}
  60.  	}
  61.  	return root;
  62.  }
  63. int main() {
  64. 	TreeNode* root = buildTree();
  65.    /** TreeNode* root = new TreeNode(1);
  66.     root->left = new TreeNode(2);
  67.     root->right = new TreeNode(3);
  68.     root->left->left = new TreeNode(4);
  69.     root->left->right = new TreeNode(5);
  70.     **/
  71.     vector<vector<int>>ans = treeTraversal(root);
  72.     for(int val : ans[0])cout<<val<<" ";
  73.     cout<<endl;
  74.     cout<<"in"<<endl;
  75.     for(int val : ans[1])cout<<val<<" ";
  76.     cout<<endl;
  77.     cout<<"post"<<endl;
  78.     for(int val : ans[2])cout<<val<<" ";
  79.     cout<<endl;
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1 2 3 4 5 -1 -1
stdout
copy 
4 2 5 1 3 
in
1 2 4 5 3 
post
4 5 2 3 1
https://ideone.com/MC09NL
language:
C++14 (gcc 8.3)
created:
2 hours 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!