Here, We see Construct Binary Tree from Preorder and Inorder 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 Preorder and Inorder Traversal LeetCode Solution
Table of Contents
Problem Statement
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]
Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution C++
class Solution {
public:
TreeNode* constructTree(vector < int > & preorder, int preStart, int preEnd, vector
< int > & inorder, int inStart, int inEnd, map < int, int > & mp) {
if (preStart > preEnd || inStart > inEnd) return NULL;
TreeNode* root = new TreeNode(preorder[preStart]);
int elem = mp[root -> val];
int nElem = elem - inStart;
root -> left = constructTree(preorder, preStart + 1, preStart + nElem, inorder,
inStart, elem - 1, mp);
root -> right = constructTree(preorder, preStart + nElem + 1, preEnd, inorder,
elem + 1, inEnd, mp);
return root;
}
TreeNode* buildTree(vector < int > & preorder, vector < int > & inorder) {
int preStart = 0, preEnd = preorder.size() - 1;
int inStart = 0, inEnd = inorder.size() - 1;
map < int, int > mp;
for (int i = inStart; i <= inEnd; i++) {
mp[inorder[i]] = i;
}
return constructTree(preorder, preStart, preEnd, inorder, inStart, inEnd, mp);
}
};
Code language: PHP (php)
Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution Java
class Solution {
private int i = 0;
private int p = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Integer.MIN_VALUE);
}
private TreeNode build(int[] preorder, int[] inorder, int stop) {
if (p >= preorder.length) {
return null;
}
if (inorder[i] == stop) {
++i;
return null;
}
TreeNode node = new TreeNode(preorder[p++]);
node.left = build(preorder, inorder, node.val);
node.right = build(preorder, inorder, stop);
return node;
}
}
Code language: PHP (php)
Construct Binary Tree from Preorder and Inorder Traversal Solution JavaScript
var buildTree = function(preorder, inorder) {
p = i = 0
build = function(stop) {
if (inorder[i] != stop) {
var root = new TreeNode(preorder[p++])
root.left = build(root.val)
i++
root.right = build(stop)
return root
}
return null
}
return build()
};
Code language: JavaScript (javascript)
Construct Binary Tree from Preorder and Inorder Traversal Solution Python
class Solution(object):
def buildTree(self, preorder, inorder):
VAL_TO_INORDER_IDX = {inorder[i]: i for i in range(len(inorder))}
def buildTreePartition(preorder, inorder_start, inorder_end):
if not preorder or inorder_start < 0 or inorder_end > len(inorder):
return None
root_val = preorder[0]
root_inorder_idx = VAL_TO_INORDER_IDX[root_val]
if root_inorder_idx > inorder_end or root_inorder_idx < inorder_start:
return None
root = TreeNode(preorder.pop(0))
root.left = buildTreePartition(preorder, inorder_start, root_inorder_idx - 1)
root.right = buildTreePartition(preorder, root_inorder_idx + 1, inorder_end)
return root
return buildTreePartition(preorder, 0, len(inorder) - 1)
Code language: HTML, XML (xml)