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

Construct Binary Tree from Preorder and Postorder Traversal

Medium TreeBinary TreeDFS LeetCode

You're given two arrays, preorder and postorder, holding the preorder and postorder traversals of the same binary tree whose node values are all distinct. Return any binary tree with these traversals. The original shape is not necessarily unique.

Input Format
Implement constructFromPrePost(preorder, postorder). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Returned trees are displayed as level-order arrays, trimming trailing nulls. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 ยท Run Sample

Input
preorder = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]
Output
[1,2,3,4,5,6,7]

Example 2

Input
preorder = [1]
postorder = [1]
Output
[1]
Constraints
  • 1 <= preorder.length <= 30
  • preorder and postorder are permutations of 1..n
Test Cases (2)
Case 1
Args: [[1,2,4,5,3,6,7],[4,5,2,6,7,3,1]] Expected: [1,2,3,4,5,6,7]
Case 2
Args: [[1],[1]] Expected: [1]
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.

javascript
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