Formatted question description: https://leetcode.ca/all/889.html

# 889. Construct Binary Tree from Preorder and Postorder Traversal

Medium

## 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

The preorder traversal visits the binary tree in such an order: root, left subtree, and right subtree. For each subtree, the nodes are also visited in the order of preorder traversal.

The postorder traversal visits the binary tree in such an order: left subtree, right subtree, and root. For each subtree, the nodes are also visited in the order of postorder traversal.

This problem can be solved using recursion. Base cases are when the number of nodes is 0 or 1. If the number of nodes is 0, then return null. If the number of nodes is 1, then create the root using the value of the node, and return the root.

If the number of nodes is greater than 1, suppose the left child always exist. The element pre is the value of the left child of the root. Find the value pre in post, which is the last node to be visited in the left subtree in postorder traversal, and the number of nodes in the left subtree can be obtained. The number of nodes in the right subtree can be obtained as well. Then use the subarrays of pre and post to create the left subtree and the right subtree respectively. Finally, return the root.

Java

Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
int length = pre.length;
if (length == 0)
return null;
else if (length == 1)
return new TreeNode(pre);
else {
TreeNode root = new TreeNode(pre);
int leftChild = pre;
int leftCount = 0;
for (int i = 0; i < length; i++) {
if (post[i] == leftChild) {
leftCount = i + 1;
break;
}
}
root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1 + leftCount), Arrays.copyOfRange(post, 0, leftCount));
root.right = constructFromPrePost(Arrays.copyOfRange(pre, 1 + leftCount, length), Arrays.copyOfRange(post, leftCount, length - 1));
return root;
}
}
}