ES6 solution


  • 0
    Y

    This took me a long time to figure out, since the parameters are reversed from https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/.

    function buildInOrderIndex(inOrder) {
      const index = new Map()
      for (let i = 0; i < inOrder.length; i++) {
        // no overwriting can occur since we assume distinct keys
        index.set(inOrder[i], i)
      }
      return index
    }
    
    function buildTree(
      inOrder,
      postOrder,
      inOrderIndex = buildInOrderIndex(inOrder),
      inOrderStart = 0,
      inOrderEnd = inOrder.length,
      postOrderStart = 0,
      postOrderEnd = postOrder.length
    ) {
      if (inOrderStart >= inOrderEnd || postOrderStart >= postOrderEnd) {
        return null
      }
      const nextRoot = new TreeNode(postOrder[postOrderEnd - 1])
      const nextRootIndex = inOrderIndex.get(nextRoot.val)
      nextRoot.left = buildTree(
        inOrder,
        postOrder,
        inOrderIndex,
        inOrderStart,
        nextRootIndex,
        postOrderStart,
        postOrderEnd - (inOrderEnd - nextRootIndex)
      )
      nextRoot.right = buildTree(
        inOrder,
        postOrder,
        inOrderIndex,
        nextRootIndex + 1,
        inOrderEnd,
        postOrderEnd - (inOrderEnd - nextRootIndex),
        postOrderEnd - 1
      )
      return nextRoot
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.