# 889. Construct Binary Tree from Preorder and Postorder Traversal

[Leetcode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)

Given two integer arrays, `preorder` and `postorder` where `preorder` is the preorder traversal of a binary tree of **distinct** values and `postorder` is the postorder traversal of the same tree, reconstruct and return *the binary tree*.

If there exist multiple answers, you can **return any** of them.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/07/24/lc-prepost.jpg)

```
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]
```

&#x20;

**Constraints:**

* `1 <= preorder.length <= 30`
* `1 <= preorder[i] <= preorder.length`
* All the values of `preorder` are **unique**.
* `postorder.length == preorder.length`
* `1 <= postorder[i] <= postorder.length`
* All the values of `postorder` are **unique**.
* It is guaranteed that `preorder` and `postorder` are the preorder traversal and postorder traversal of the same binary tree.

### Basic Idea:

首先我们可以注意到在preorder中每次都是root在最前面，而在postorder中root则会在最后面，利用这个性质我们可以递归地每次将左右子树所对应的array分离出来，然后递归调用求解。

例如对于上图中的例子

```
preorder:   [1,  2,4,5,  3,6,7], 
postorder = [4,5,2,  6,7,3,  1]

在第一层中，我们可以知道当前层对应的node为1，然后2一定是下一层subtree的root，然后在postorder
中找到2的为止，接下来我们就知道左子树对应的数组为[245]和[452], 右子树则是剩下的[367]和[673]。

那么如果没有左子树，只有右子树呢？这种情况下我们无法分辨唯一的子树是左边还是右边，可以只将其当作
左子树。
```

#### Java Code:

```java
// 1 245 367
// 452 673 1
//   |
//  mid
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int[] post, int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        if (preStart == preEnd) return new TreeNode(pre[preStart]);
        TreeNode root = new TreeNode(pre[preStart]);
        int mid = postStart;
        while (post[mid] != pre[preStart + 1]) mid++;
        root.left = build(pre, post, preStart + 1, preStart + (mid - postStart) + 1, postStart, mid);
        root.right = build(pre, post, preStart + (mid - postStart) + 2, preEnd, mid + 1, postEnd - 1);
        return root;
    }
}
```
