Leetcode Problem 106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Leetcode Solutions

Construct Binary Tree from Inorder and Postorder Traversal

  1. Create a hashmap to map each value in the inorder sequence to its index.
  2. Define a recursive function buildTreeHelper that takes the current range of inorder sequence to consider.
  3. If the current inorder range is empty, return None.
  4. Take the last element from the remaining postorder sequence as the root.
  5. Find the root's index in the inorder sequence using the hashmap.
  6. Recursively call buildTreeHelper for the left subtree with the inorder range before the root's index.
  7. Recursively call buildTreeHelper for the right subtree with the inorder range after the root's index.
  8. Construct the current root node with the left and right subtrees obtained from the recursive calls.
  9. Return the constructed root node.
UML Thumbnail

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...