Construct Binary Tree from Preorder and Postorder Traversal Medium 0 attempts
LeetCode ↗

Construct Binary Tree from Preorder and Postorder Traversal

Medium TreeBinary TreeDFS LeetCode

Given preorder and postorder traversal arrays of a binary tree with distinct values, reconstruct the tree.

Example: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] → Output: [1,2,3,4,5,6,7]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= preorder.length <= 30
  • preorder and postorder are permutations of 1..n
Topics
TreeBinary TreeDFS

Recursive Construction

The first element of preorder is root, the second is the left subtree root. Find it in postorder to determine left subtree size.

function constructFromPrePost(preorder, postorder) {
  let preIdx = 0;
  const postMap = new Map();
  postorder.forEach((v, i) => postMap.set(v, i));
  function build(postLo, postHi) {
    if (postLo > postHi || preIdx >= preorder.length) return null;
    const node = { val: preorder[preIdx++], left: null, right: null };
    if (postLo === postHi) return node;
    const leftRootIdx = postMap.get(preorder[preIdx]);
    node.left = build(postLo, leftRootIdx);
    node.right = build(leftRootIdx + 1, postHi - 1);
    return node;
  }
  return build(0, postorder.length - 1);
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript