Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Construct a binary tree from in-order and post-order arrays. The requirement is to understand in-order and post-order traversal. In-Order visits all nodes to the left, then the current node and then all nodes to the right. Post-order visits all nodes to the left of the current node, all nodes to the right of the current node and finally the node itself. This means, that the root node can immediately identified as the last element in the postorder array. From there we can split the inorder array by getting the index of the element and immediately know that all nodes to the left of the pivot element belong to the left of the item and vice versa. By simply counting the number of elements, we where we need to split the postorder array. Finally, apply this knowledge in a recursive method (inner) and stop once postorder (or inorder) is empty. Then we know we are below a leaf node.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    return self.inner(inorder, postorder)
  
  def inner(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    if len(postorder) == 0:
      return None
    val = postorder.pop()
    root = TreeNode(val=val)
    idx = inorder.index(val)
    root.left = self.inner(inorder[:idx], postorder[:idx])
    root.right = self.inner(inorder[idx+1:], postorder[idx:])
    return root