It’s day 27 of the Leetcode July Challenge and I’ve had a long day at work and came home to this problem that I haven’t really enjoyed very much. We’re given the inorder and postorder traversal values of an unknown binary tree and asked to construct the tree and return its root. I’m going to skip much detailed discussion for now–may come back to it at a later date, and will leave looking at today’s code as an exercise for the reader. Really, let me know if you have any questions or have improvement suggestions. Here’s a recursive and iterative algorithm, both of which are pretty good, O(n), but still somewhat unrefined.

Recursive

TreeNode* buildTree(vector<int> &inorder, vector<int> &postorder) {
   unordered_map<int, int> inorderMap;
   for (int i = 0; i < inorder.size(); ++i) {
	  inorderMap[inorder[i]] = i;
   }
   return build(postorder, 0, postorder.size()-1, inorderMap, 0, inorder.size()-1);
}

TreeNode* build(vector<int>& postorder, int postleft, int postright, unordered_map<int, int>& inorderMap, int inleft, int inright) {
   if(postleft > postright || inleft > inright) return nullptr;
   
   int rootVal = postorder[postright];
   TreeNode* root = new TreeNode(rootVal);
   int rootIndex = inorderMap.find(rootVal)->second;

   int leftSubtreeSize = rootIndex - inleft;
   
   root->left = build(postorder, postleft, postleft+leftSubtreeSize-1, inorderMap, inleft, inleft+leftSubtreeSize-1);
   root->right = build(postorder, postleft+leftSubtreeSize, postright-1, inorderMap, inleft+leftSubtreeSize+1, inright);
   
   return root;
}

Iterative

TreeNode* buildTree(vector<int> &inorder, vector<int> &postorder) {
   if(inorder.empty()) return nullptr;
   
   TreeNode* root = new TreeNode(postorder.back());
   postorder.pop_back();
   
   stack<TreeNode*> nodeStack;
   nodeStack.push(root);
   
   while(!nodeStack.empty())
   {            
	  if(nodeStack.top()->val == inorder.back())
	  {
		 TreeNode* parent = nodeStack.top();
		 nodeStack.pop();
		 inorder.pop_back();
		 
		 if(inorder.empty()) break;
		 if(!nodeStack.empty() && nodeStack.top()->val == inorder.back()) continue;
		 
		 parent->left = new TreeNode(postorder.back());
		 postorder.pop_back();
		 nodeStack.push(parent->left);
	  }
	  else
	  {
		 nodeStack.top()->right = new TreeNode(postorder.back());
		 postorder.pop_back();
		 nodeStack.push(nodeStack.top()->right);
	  }
   }
	return root;
}