🎨Now live: Try our Free AI Image Generation Feature

Intuition
Preorder and inorder traversals provide sufficient information to uniquely determine a binary tree. The first element in the preorder traversal is the root of the tree. In the inorder traversal, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree. Using this information, we can recursively construct the binary tree.
Approach
- Initialization:
- Use two indices,
p
for thepreorder
array andi
for theinorder
array. - Initialize these indices to zero. - Recursive Tree Construction:
- Define a helper function
build(stop)
that builds the tree up to a givenstop
value from theinorder
array. - In the helper function: - If the currentinorder
value matches thestop
value, returnNone
. - Create a newTreeNode
with the current value frompreorder
and increment thepreorder
index (p
). - Recursively build the left subtree using the current root value as the newstop
value. - Increment theinorder
index (i
). - Recursively build the right subtree using the initialstop
value. - Return the root node. - Main Function:
- Call the
build
function with the initial stop valueNone
to construct the entire tree.
Complexity
Time Complexity:
O(N)
where N
is the number of nodes in the tree. Each node is visited once during the traversal.
Space Complexity:
O(N)
for the recursion stack in the worst case of a completely unbalanced tree.
Code
C++
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
int p = 0, i = 0;
return build(preorder, inorder, p, i, INT_MAX);
}
private:
TreeNode* build(vector& preorder, vector& inorder, int& p, int& i, int stop) {
if (i < inorder.size() && inorder[i] != stop) {
TreeNode* root = new TreeNode(preorder[p++]);
root->left = build(preorder, inorder, p, i, root->val);
i++;
root->right = build(preorder, inorder, p, i, stop);
return root;
}
return nullptr;
}
};
Python
class Solution:
def __init__(self):
self.p = 0
self.i = 0
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def build(stop):
if self.i < len(inorder) and inorder[self.i] != stop:
root = TreeNode(preorder[self.p])
self.p += 1
root.left = build(root.val)
self.i += 1
root.right = build(stop)
return root
return None
return build(None)
Java
class Solution {
private int p = 0;
private int i = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, Integer.MAX_VALUE);
}
private TreeNode build(int[] preorder, int[] inorder, int stop) {
if (i < inorder.length && inorder[i] != stop) {
TreeNode root = new TreeNode(preorder[p++]);
root.left = build(preorder, inorder, root.val);
i++;
root.right = build(preorder, inorder, stop);
return root;
}
return null;
}
}
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()
};