106. Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

link: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]

Input: inorder = [-1], postorder = [-1] Output: [-1]

Solution Approach

The solution utilizes the properties of inorder and postorder traversals of a binary tree to reconstruct the tree by recursively determining the root from the postorder and then using the inorder to segregate left and right subtrees.

Algorithm

1. Determine Root: The last element of postorder traversal gives us the root of the tree.
2. Identify Left and Right Subtrees: Using the root from postorder, find the root in inorder traversal. Everything to the left of this root in inorder will form the left subtree and everything to the right will form the right subtree.
3. Recurse: Recursively apply the above steps on the left and right subtree segments to construct the complete tree.

Implement

    class Solution:
      def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
          def build(ini, inj, posti, postj):
              if ini == inj:
                  return TreeNode(inorder[ini])
              rootval = postorder[postj]
              ind = dic[rootval]
              res = TreeNode(rootval)

              #leftnode
              leftin1 = ini
              rightin1 = ind - 1
              leftpost1 = posti
              rightpost1 = posti + rightin1 - leftin1

              #rightnode
              leftin2 = ind + 1
              rightin2 = inj
              leftpost2 = rightpost1 + 1
              rightpost2 = postj - 1

              if leftin1 <= rightin1:
                  res.left = build(leftin1, rightin1, leftpost1, rightpost1)
              if leftin2 <= rightin2:
                  res.right = build(leftin2, rightin2, leftpost2, rightpost2)
              return res
          
          dic = {n: i for i, n in enumerate(inorder)}
          if not inorder:
              return None
          return build(0, len(inorder) - 1, 0, len(postorder) - 1)
 

    
    

Twitter  facebook  Email