# C++ O(n) Time / O(logn) Space Recursive Solution: Beats 98% submission

• Core Idea:

When you reverse the postorder, it has 'root->right->left' order, which is very similar to preorder. Then you want to revert inorder as well to have 'right->root->left' order. Now you can think it as same problem with "Construct Tree Using Preorder and Inorder", only changing left tree to right tree.

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || inorder.size() != postorder.size())
return nullptr;

// now post order becomes preorder like: root->right->left
reverse(postorder.begin(), postorder.end());
// inorder is still inorder but start from right: right->root->left
reverse(inorder.begin(), inorder.end());
stack<TreeNode*> st;
TreeNode* node = new TreeNode(postorder[0]);
TreeNode* root = node;
int poIdx = 1;
int inIdx = 0;
for (; poIdx < postorder.size(); ++poIdx) {
TreeNode* newNode = new TreeNode(postorder[poIdx]);
if (inorder[inIdx] != node->val) {
node->right = newNode;
st.push(node);
node = newNode;
} else {
++inIdx;
while (!st.empty() && inorder[inIdx] == st.top()->val) {
++inIdx;
node = st.top();
st.pop();
}

node->left = newNode;
node = newNode;
}
}

return root;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.