# Problem

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: Recursion

pre = [(root) (left-child) (right-child)]

post = [(left-child) (right-child) (root)]

We need to recursively find the first node in pre.left-child from post.left-child

e.g.

pre = [(1), (2,4,5), (3,6,7)]

post = [(4,5,2), (6,7,3), (1)]

First element of left-child is 2 and the length of it is 3.

root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))

Time complexity: O(n^2)

Space complexity: O(n)

Time complexity: O(n^2)

Space complexity: O(n)

Time complexity: O(n)

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode

## Be First to Comment

Mission News Theme by Compete Themes.