fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6.  
  7.   struct TreeNode {
  8.       int val;
  9.       TreeNode *left;
  10.       TreeNode *right;
  11.       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  12.   };
  13.  
  14.  
  15. class Solution {
  16. private:
  17.     int inorderSearch(vector<int> &inorder, int inStrt, int inEnd, int target) {
  18.         for(int i = inStrt ; i <= inEnd ; i++ ) {
  19.             if(inorder[i] == target)
  20.                return i ;
  21.         }
  22.     }
  23.  
  24.     TreeNode *buildTreeUtil(vector<int> &postorder, vector<int> &inorder, int inStrt, int inEnd, int& postIndex) {
  25.         if(inStrt > inEnd)
  26.            return NULL ;
  27.         TreeNode *root = new TreeNode(postorder[postIndex--]) ;
  28.         if(inStrt == inEnd)
  29.            return root ;
  30.         int inIndex = inorderSearch(inorder, inStrt, inEnd, root -> val ) ;
  31.         root -> left = buildTreeUtil(postorder, inorder, inStrt, inIndex - 1, postIndex) ;
  32.         root -> right = buildTreeUtil(postorder, inorder, inIndex + 1 , inEnd, postIndex) ;
  33.         return root ;
  34.     }
  35.  
  36. public:
  37.     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
  38.         int inStrt = 0 ;
  39.         int inEnd = postorder.size() - 1 ;
  40.         int postIndex = inEnd ;
  41.         TreeNode *root = NULL ;
  42.         root = buildTreeUtil(postorder, inorder, inStrt, inEnd, postIndex) ;
  43.         return root ;
  44.     }
  45.  
  46.     void Inorder(TreeNode *root) {
  47.     	if(!root)
  48.     	   return ;
  49.     	Inorder(root -> left) ;
  50.     	cout << root -> val << " " ;
  51.     	Inorder(root -> right) ;
  52.     }
  53.  
  54.     void Postorder(TreeNode *root) {
  55.     	if(!root)
  56.     	   return ;
  57.     	Postorder(root -> left) ;
  58.     	Postorder(root -> right) ;
  59.     	cout << root -> val << " " ;
  60.     }
  61.  
  62.     void Preorder(TreeNode *root) {
  63.     	if(!root)
  64.     	   return ;
  65.     	cout << root -> val << " " ;
  66.     	Preorder(root -> left) ;
  67.     	Preorder(root -> right) ;
  68.     }
  69.  
  70.     void DFS(struct TreeNode *root , vector<int> v, int& minHeight) ;
  71.  
  72. };
  73.  
  74. void Solution :: DFS (struct TreeNode *root , vector<int> v, int& minHeight) {
  75. 	if(!root)
  76. 	   return ;
  77. 	v.push_back(root -> val) ;
  78. 	if(!(root -> left) && !(root -> right) ) {
  79.  
  80. 		if(minHeight > v.size())
  81. 		   minHeight = v.size() ;
  82. 		//for(int i = 0 ; i < v.size() ; i++)
  83. 		  // cout << v[i] << " " ;
  84. 		//cout << endl ;
  85. 	}
  86. 	DFS(root -> left , v, minHeight) ;
  87. 	DFS(root -> right , v, minHeight) ;
  88. 	v.pop_back() ;
  89. }
  90.  
  91. int main() {
  92. 	Solution s ;
  93. //	vector<int> v ;
  94. //	int minHeight = INT_MAX ;
  95. 	vector<int> preorder , inorder , postorder ;
  96. //  preorder.push_back(1);preorder.push_back(2);preorder.push_back(3);preorder.push_back(7);preorder.push_back(8);preorder.push_back(4);preorder.push_back(5);preorder.push_back(6);
  97. //  inorder.push_back(3);inorder.push_back(2);inorder.push_back(8);inorder.push_back(7);inorder.push_back(1);inorder.push_back(5);inorder.push_back(6);inorder.push_back(4);
  98.     inorder.push_back(1);inorder.push_back(2);inorder.push_back(3);inorder.push_back(4);inorder.push_back(5);
  99.     postorder.push_back(1);postorder.push_back(2);postorder.push_back(5);postorder.push_back(4);postorder.push_back(3);
  100.     TreeNode *root = NULL ;
  101. //  root = s . buildTree(preorder, inorder) ;
  102.     root = s . buildTree(inorder, postorder) ;
  103.     s . Postorder(root);
  104. //    cout << endl << "Paths :\n" ;
  105. //    s.DFS(root , v , minHeight) ; 
  106. //    cout << minHeight ;
  107. 	return 0;
  108. }
Runtime error #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RTITZd
language:
C++14 (gcc 8.3)
created:
9 years 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!