Here, We see Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution
Table of Contents
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:
![tree](https://i0.wp.com/assets.leetcode.com/uploads/2021/02/19/tree.jpg?w=1400&ssl=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]
Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution 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;
}
};
Code language: PHP (php)
Construct Binary Tree from Inorder and Postorder Traversal Leetcode Solution 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;
}
}
Code language: PHP (php)
Construct Binary Tree from Inorder and Postorder Traversal Leetcode Solution 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);
};
Code language: JavaScript (javascript)
Construct Binary Tree from Inorder and Postorder Traversal Leetcode Solution 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