Algorithm
Problem Nmae: 105. Construct Binary Tree from Preorder and Inorder Traversal
problem Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int *preorder;
int pre_idx;
int pre_sz;
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->preorder[data->pre_idx ++];
i = start;
while (i < end && data->inorder[i] != node->val) i ++;
node->left = make_tree(data, start, i);
node->right = make_tree(data, i + 1, end);
return node;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
data_t data;
data.preorder = preorder;
data.pre_idx = 0;
data.pre_sz = preorderSize;
data.inorder = inorder;
return make_tree(&data, 0, inorderSize);
}
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map < int, int>m;
for(int i = 0; i < inorder.size(); i++) m[inorder[i]] = i;
return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, m);
}
TreeNode* helper(vector<int>& preorder, int pStart, int pEnd, vector<int>& inorder, int iStart, int iEnd, unordered_map < int, int>& m) {
if(pStart > pEnd) return NULL;
TreeNode* root = new TreeNode(preorder[pStart]);
int i = m[preorder[pStart]];
root->left = helper(preorder, pStart + 1, pStart + i - iStart, inorder, iStart, i - 1, m);
root->right = helper(preorder, pStart + i - iStart + 1, pEnd, inorder, i + 1, iEnd, m);
return root;
}
};
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map map = new HashMap<>();
int[] preorderIndex = {0};
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1, map, preorderIndex);
}
private TreeNode buildTree(int[] preorder, int left, int right, Map < Integer, Integer> map, int[] preorderIndex) {
if (left > right) {
return null;
}
int rootVal = preorder[preorderIndex[0]++];
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(preorder, left, map.get(rootVal) - 1, map, preorderIndex);
root.right = buildTree(preorder, map.get(rootVal) + 1, right, map, preorderIndex);
return root;
}
}
Input
preorder = [-1], inorder = [-1]
Output
[-1]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const buildTree = function(preorder, inorder) {
if(preorder.length === 0 && inorder.length === 0) return null
const val = preorder[0]
const node = new TreeNode(val)
const inIdx = inorder.indexOf(val)
const leftIn = inorder.slice(0, inIdx)
const rightIn = inorder.slice(inIdx + 1)
const leftPre = preorder.slice(1, leftIn.length + 1)
const rightPre = preorder.slice(leftIn.length + 1)
// console.log(leftIn, rightIn, leftPre, rightPre)
node.left = buildTree(leftPre, leftIn)
node.right = buildTree(rightPre, rightIn)
return node
};
Input
preorder = [-1], inorder = [-1]
Output
[-1]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def buildTree(self, preorder, inorder):
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[0:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _105_ConstructBinaryTreeFromPreorderAndInorderTraversal
{
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
if (preorder.Length == 0 || inorder.Length == 0) return null;
return BuildTree(preorder, 0, preorder.Length, inorder, 0, inorder.Length);
}
private TreeNode BuildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd)
{
var root = new TreeNode(preorder[preorderStart]);
var inorderIndex = inorderStart;
for (; inorderIndex < inorderEnd; inorderIndex++)
if (inorder[inorderIndex] == preorder[preorderStart])
break;
var leftLength = inorderIndex - inorderStart;
if (leftLength > 0)
root.left = BuildTree(preorder, preorderStart + 1, preorderStart + 1 + leftLength, inorder, inorderStart, inorderIndex);
if (inorderEnd > inorderIndex + 1)
root.right = BuildTree(preorder, preorderStart + 1 + leftLength, preorderEnd, inorder, inorderIndex + 1, inorderEnd);
return root;
}
}
}
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]