# O(n) recursive solution without hashmap nor index

• python solution:

``````class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
def postdfs(stop):
if postorder and inorder[-1] != stop:
root = TreeNode(postorder.pop())
root.right = postdfs(root.val)
inorder.pop()
root.left = postdfs(stop)
return root
inorder, postorder = inorder[:], postorder[:]
return postdfs(None)

# 202 / 202 test cases passed.
# Status: Accepted
# Runtime: 62 ms
# beats 97.20 %
``````

c++ solution:

``````/**
* 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) {
vector<int> in(inorder), post(postorder);
return postdfs(in, post, (TreeNode *)NULL);
}

TreeNode * postdfs(vector<int> & in, vector<int> & post, TreeNode * stop) {
if ( post.empty() || (stop && in.back() == stop->val) ) {
return NULL;
}
TreeNode * root = new TreeNode(post.back());
post.pop_back();
root->right = postdfs(in, post, root);
in.pop_back();
root->left = postdfs(in, post, stop);
return root;
}
};

// 202 / 202 test cases passed.
// Status: Accepted
// Runtime: 9 ms
// beats 91.06 %
``````

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