Construct Binary Tree from Preorder and Postorder Traversal

Description

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

 

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

 

Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, ..., pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Solution(javascript)

const constructFromPrePost = function (pre = [], post = []) {
  const aux = (currentPre = pre, currentPost = post) => {
    if (currentPre.length === 0) {
      return null
    }
    if (currentPre.length === 1) {
      return new TreeNode(currentPre[0])
    }
    const node = new TreeNode(currentPre[0])
    const index = currentPost.findIndex(v => v === currentPre[1])
    node.left = aux(
      currentPre.slice(1, index + 2),
      currentPost.slice(0, index + 1),
    )
    node.right = aux(
      currentPre.slice(index + 2),
      currentPost.slice(index + 1, currentPost.length - 1),
    )
    return node
  }
  return aux(pre, post)
}