Algorithm
Problem Nmae: 106. Construct Binary Tree from Inorder and Postorder Traversal
problem Link: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
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]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int *postorder;
int post_idx;
int *inorder;
} data_t;
struct TreeNode *make_tree(data_t *data, int start, int end) {
struct TreeNode *node;
int i;
if (start == end) return NULL;
node = malloc(sizeof(struct TreeNode));
//assert(node);
node->val = data->postorder[-- data->post_idx];
i = start;
while (i < end && data->inorder[i] != node->val) i ++;
node->right = make_tree(data, i + 1, end);
node->left = make_tree(data, start, i);
return node;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
data_t data;
data.postorder = postorder;
data.post_idx = postorderSize;
data.inorder = inorder;
return make_tree(&data, 0, inorderSize);
}
Input
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output
[3,9,20,null,null,15,7]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
Map map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
int[] postIdx = {postorder.length - 1};
return helper(postorder, map, 0, inorder.length - 1, postIdx);
}
private TreeNode helper(int[] postorder, Map < Integer, Integer> map, int leftIdx, int rightIdx, int[] postIdx) {
if (leftIdx > rightIdx) {
return null;
}
TreeNode root = new TreeNode(postorder[postIdx[0]--]);
int index = map.get(root.val);
root.right = helper(postorder, map, index + 1, rightIdx, postIdx);
root.left = helper(postorder, map, leftIdx, index - 1, postIdx);
return root;
}
}
Input
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output
[3,9,20,null,null,15,7]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const buildTree = function(inorder, postorder) {
const inmap = {};
const posts = postorder;
for (let i = 0; i < inorder.length; i++) {
inmap[inorder[i]] = i;
}
return helper(postorder.length - 1, 0, inorder.length - 1);
function helper(postEnd, inStart, inEnd) {
if (postEnd < 0 || inEnd < inStart) return null;
const val = posts[postEnd];
const idx = inmap["" + val];
const root = new TreeNode(val);
root.left = helper(postEnd - (inEnd - idx) - 1, inStart, idx - 1);
root.right = helper(postEnd - 1, idx + 1, inEnd);
return root;
}
};
Input
inorder = [-1], postorder = [-1]
Output
[-1]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def buildTree(self, inorder, postorder):
if inorder:
ind = inorder.index(postorder.pop())
root = TreeNode(inorder[ind])
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root
Input
inorder = [-1], postorder = [-1]
Output
[-1]
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _106_ConstructBinaryTreeFromInorderAndPostorderTraversal
{
public TreeNode BuildTree(int[] inorder, int[] postorder)
{
if (inorder.Length == 0 || postorder.Length == 0) return null;
return BuildTree(inorder, 0, inorder.Length, postorder, 0, postorder.Length);
}
private TreeNode BuildTree(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd)
{
var root = new TreeNode(postorder[postorderEnd - 1]);
var inorderIndex = inorderStart;
for (; inorderIndex < inorderEnd; inorderIndex++)
if (inorder[inorderIndex] == postorder[postorderEnd - 1])
break;
var leftLength = inorderIndex - inorderStart;
if (leftLength > 0)
root.left = BuildTree(inorder, inorderStart, inorderIndex, postorder, postorderStart, postorderStart + leftLength);
if (inorderEnd > inorderIndex + 1)
root.right = BuildTree(inorder, inorderIndex + 1, inorderEnd, postorder, postorderStart + leftLength, postorderEnd - 1);
return root;
}
}
}
Input
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output
[3,9,20,null,null,15,7]