Last updated on January 10th, 2025 at 05:06 am
Here, we see a Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Ordered Map
Companies
Level of Question
Medium
Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution
Table of Contents
1. Problem Statement
Given two integer arrays inorder 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.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Tree Depth First Search (DFS)”. This is because the code recursively traverses the tree in a depth-first manner to construct the binary tree from the given inorder and postorder traversal arrays.
3. Code Implementation in Different Languages
3.1 Construct Binary Tree from Inorder and Postorder Traversal C++
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> index;
for (int i = 0; i < inorder.size(); i++) {
index[inorder[i]] = i;
}
return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, index);
}
TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd, unordered_map<int, int>& index) {
if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
return nullptr;
}
int rootVal = postorder[postorderEnd];
TreeNode* root = new TreeNode(rootVal);
int inorderRootIndex = index[rootVal];
int leftSubtreeSize = inorderRootIndex - inorderStart;
root->left = buildTreeHelper(inorder, postorder, inorderStart, inorderRootIndex - 1, postorderStart, postorderStart + leftSubtreeSize - 1, index);
root->right = buildTreeHelper(inorder, postorder, inorderRootIndex + 1, inorderEnd, postorderStart + leftSubtreeSize, postorderEnd - 1, index);
return root;
}
};
3.2 Construct Binary Tree from Inorder and Postorder Traversal Java
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
int rightSize = inEnd - rootIndex;
root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightSize, postEnd - 1);
return root;
}
}
3.3 Construct Binary Tree from Inorder and Postorder Traversal JavaScript
var buildTree = function(inorder, postorder) {
let hash = {};
for (let i=0;i<inorder.length;i++) hash[inorder[i]] = i;
let recur = function(start, end) {
if (start > end) return null;
let val = postorder.pop();
let root = new TreeNode(val);
root.right = recur(hash[val] + 1, end);
root.left = recur(start, hash[val] - 1);
return root;
}
return recur(0, inorder.length - 1);
};
3.4 Construct Binary Tree from Inorder and Postorder Traversal Python
class Solution(object):
def buildTree(self, inorder, postorder):
if not inorder:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
root.right = self.buildTree(inorder[inorder_index+1:], postorder)
root.left = self.buildTree(inorder[:inorder_index], postorder)
return root
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n2) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n2) | O(n2) |
- The C++ and JavaScript implementations are more efficient than Java and Python because they use a hash map to store the indices of the
inorderarray, allowing for O(1) lookups. - The Python implementation is the least efficient due to the use of array slicing, which creates new arrays at each recursive call, leading to higher space complexity.