# 889.Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal

## 889. Construct Binary Tree from Preorder and Postorder Traversal

## 题目地址

<https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/>

## 题目描述

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

## 代码

### Approach #1 Recursion

Time: O(N^2) && Space: O(N^2)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int N = pre.length;
    if (N == 0)        return null;
    TreeNode root = new TreeNode(pre[0]);
    if (N == 1)        return root;

    int L = 0;
    for (int i = 0; i < N; i++) {
      if (post[i] == pre[1])
        L = i + 1;
    }

    root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, L+1), 
                                                                    Arrays.copyOfRange(post, 0, L));

    root.right = constructFromPrePost(Arrays.copyOfRange(pre, L+1, N),
                                     Arrays.copyOfRange(post, L, N-1));

    return root;
  }
}
```

### Approach #2

Create a node `TreeNode(pre[preIndex])` as the root.

Becasue root node will be lastly iterated in post order, `if root.val == post[posIndex]`, it means we have constructed the whole tree,

If we haven't completed constructed the whole tree, So we recursively `constructFromPrePost` for left sub tree and right sub tree.

And finally, we'll reach the `posIndex` that `root.val == post[posIndex]`. We increment `posIndex` and return our `root` node.

```java
class Solution {
  int preIndex = 0;
  int postIndex = 0;
  public TreeNode constructFromPrePost(int[] pre, int[] post) {
    TreeNode root = new TreeNode(pre[preIndex++]);
    if (root.val != post[postIndex])
      root.left = constructFromPrePost(pre, post);
    if (root.val != post[postIndex])
      root.right = constructFromPrePost(pre, post);

    postIndex++;
    return root;
  }
}
```

### Approach #3 Iterative

O(N)

```java
class Solution {
  public TreeNode constructFromPrePost(int[] pre, int[] post) {
    Deque<TreeNode> s = new ArrayDeque<>();
    s.offer(new TreeNode(pre[0]));
    for (int i = 1, j = 0; i < pre.length; i++) {
      TreeNode node = new TreeNode(pre[i]);
      while (s.getLast().val == post[j]) {
        s.pollLast();
        j++;
      }
      if (s.getLast().left == null) {
        s.getLast().left = node;
      } else {
        s.getLast().right = node;
      }
      s.offer(node);
    }

    return s.getFirst();
  }
}
```
