cosntruct Archives - Huahua's Tech Road

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution: Recursion

Similar to LC 105

Time complexity: O(n)
Space complexity: O(n)

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[postorder[pe]];

int pm = ps + (im - is) - 1;

auto root = new TreeNode(postorder[pe]);

root->left = buildTree(is, im - 1, ps, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe - 1);

return root;

};

return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);

}

};