In this Leetcode Construct Binary Tree from Inorder and Postorder Traversal problem solution we have Given two integer arrays in order and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Problem solution in Python.
class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: in_map = {} for i in range(len(inorder)): in_map[inorder[i]] = i def func(inorder, postorder, start, end, in_map): if start >= end: if inorder == [] or start > end: return None if self.pindex >=0: node = postorder[self.pindex] self.pindex -= 1 return TreeNode(inorder[start]) else: if self.pindex >=0: node = postorder[self.pindex] self.pindex -= 1 root = TreeNode(node) idx = in_map[node] root.right = func(inorder, postorder, idx + 1, end, in_map) root.left = func(inorder, postorder,start, idx - 1, in_map) return root self.pindex = len(postorder) - 1 return func(inorder, postorder, 0, len(inorder) - 1, in_map)
Problem solution in Java.
class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return helper(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } public TreeNode helper(int []inorder,int si,int ei,int[] postorder,int ps,int pe){ if(si>ei) return null; TreeNode root=new TreeNode(postorder[pe]); int idx=si; while(idx<inorder.length && inorder[idx]!=postorder[pe]) idx++; int count=idx-si; root.left=helper(inorder,si,idx-1,postorder,ps,ps+count-1); root.right=helper(inorder,idx+1,ei,postorder,ps+count,pe-1); return root; } }
Problem solution in C++.
class Solution { public: TreeNode* buildTree(vector<int>& in, vector<int>& post) { unordered_map<int, int> pos; int n = post.size(); for (int i = 0; i < n; i++) { pos[in[i]] = i; } TreeNode* root = NULL; for (int i = n - 1; i >= 0; i--) { int num = post[i], p = pos[num]; //cout << num << ":" << p << endl; TreeNode* tr = new TreeNode(num); if (i == n - 1) { root = tr; continue; } TreeNode* node = root, *prev = NULL; while (node) { prev = node; if (pos[node->val] > p) node = node->left; else node = node->right; } node = tr; if (pos[prev->val] > p) prev->left = tr; else prev->right = tr; } return root; } };
Problem solution in C.
struct TreeNode* buildTree(int* inorder, int inlen, int* postorder, int postlen){ if(inlen == 0) return NULL; struct TreeNode* curr = malloc(sizeof(struct TreeNode)); curr->val = postorder[postlen-1]; int mid = 0; while(inorder[mid]!=curr->val) ++mid; curr->left = buildTree(&inorder[0], mid, &postorder[0], mid); curr->right = buildTree(&inorder[mid+1], inlen-mid-1, &postorder[mid], inlen-mid-1); return curr; }