Leetcode Problem 105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Leetcode Solutions

Approach: Recursion

  1. Create a hashmap to store the value to index mapping for the inorder array.
  2. Define a helper function arrayToTree that takes two indices as the range of the current subtree in the inorder array.
  3. If the range is empty, return null.
  4. Initialize the root with preorder[preorderIndex] and increment preorderIndex.
  5. Find the root index in the inorder array using the hashmap.
  6. Recursively construct the left subtree using the range before the root index in the inorder array.
  7. Recursively construct the right subtree using the range after the root index in the inorder array.
  8. Return the root node.
  9. Call the helper function with the full range of the inorder array to construct the entire tree.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...