Dare2Solve
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.
Initialization:
p
for the preorder
array and i
for the inorder
array.Recursive Tree Construction:
build(stop)
that builds the tree up to a given stop
value from the inorder
array.inorder
value matches the stop
value, return None
.TreeNode
with the current value from preorder
and increment the preorder
index (p
).stop
value.inorder
index (i
).stop
value.Main Function:
build
function with the initial stop value None
to construct the entire tree.O(N)
where N
is the number of nodes in the tree. Each node is visited once during the traversal.
O(N)
for the recursion stack in the worst case of a completely unbalanced tree.
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int p = 0, i = 0;
return build(preorder, inorder, p, i, INT_MAX);
}
private:
TreeNode* build(vector<int>& preorder, vector<int>& 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;
}
};
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)
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;
}
}
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()
};