# Construct Binary Tree from Traversals

## [Construct Binary Tree from Preorder and Inorder Traversal](/code/tree/7-serialize-and-deserialize/construct-binary-tree-from-traversals.md)

Given preorder and inorder traversal of a tree, construct the binary tree.

**Note:** You may assume that duplicates do not exist in the tree.

For example, given

```
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
```

Return the following binary tree:

```
  3
 / \
9  20
  /  \
 15   7
```

### Note

找到subproblem，通过size来定位root，index就是inOrder中和root值相等的位置

在help function需要

```
int preStart, int inStart, int inEnd
```

|          | Left         | Right                            |
| -------- | ------------ | -------------------------------- |
| preStart | preStart + 1 | preStart + (index - inStart) + 1 |
| inStart  | inStart      | index - inStart + 1              |
| inEnd    | index - 1    | inEnd                            |

这样我们就划分了不同的左右子问题

### Code

```java
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(0, 0, inorder.length - 1, preorder, inorder);
}

private TreeNode helper(int preStart, int inStart, int inEnd,
                       int[] preorder, int[] inorder) {
    if (preStart > preorder.length - 1|| inStart > inEnd) return null;
    TreeNode root = new TreeNode(preorder[preStart]);
    int inIndex = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root.val) {
            inIndex = i;
        }
    }
    root.left  = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    root.right = helper(preStart + (inIndex - inStart) + 1, inIndex + 1, inEnd, preorder, inorder);
    return root;
}
```

## [Construct Binary Tree from Inorder and Postorder Traversal](/code/tree/7-serialize-and-deserialize/construct-binary-tree-from-traversals.md)

Given inorder and postorder traversal of a tree, construct the binary tree.

**Note:** You may assume that duplicates do not exist in the tree.

For example, given

```
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
```

Return the following binary tree:

```
    3
   / \
  9  20
    /  \
   15   7
```

### Note

类似之前的找法，不过这次我们需要从后面往前找 (inEnd should not larger than inStart)

|           | Left                              | Right         |
| --------- | --------------------------------- | ------------- |
| postStart | postStart - (inStart - Index) - 1 | postStart - 1 |
| inStart   | index - 1                         | inStart       |
| inEnd     | inEnd                             | index + 1     |

### Code

```java
public TreeNode buildTree(int[] inorder, int[] postorder) {
    return buildTree(inorder, inorder.length-1, 0, postorder, postorder.length-1);
}

private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder,
        int postStart) {
    if (postStart < 0 || inStart < inEnd)
        return null;

    //The last element in postorder is the root.
    TreeNode root = new TreeNode(postorder[postStart]);

    //find the index of the root from inorder. Iterating from the end.
    int rIndex = inStart;
    for (int i = inStart; i >= inEnd; i--) {
        if (inorder[i] == postorder[postStart]) {
            rIndex = i;
            break;
        }
    }
    //build right and left subtrees. Again, scanning from the end to find the sections.
    root.right = buildTree(inorder, inStart, rIndex + 1, postorder, postStart-1);
    root.left = buildTree(inorder, rIndex - 1, inEnd, postorder, postStart - (inStart - rIndex) -1);
    return root;
}
```

## [Construct Binary Tree from Preorder and Postorder Traversal](/code/tree/7-serialize-and-deserialize/construct-binary-tree-from-traversals.md)

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

* It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
* permutations of length, from 1 to pre.length

### Note

利用permutation这个条件，存post的位置，找preOrder根后面的第一个元素的位置，分别对划分左右

`int N = map.get(pre[preStart + 1]) - postStart;` ---- N is the length of Left subtree

|           | Left             | Right                |
| --------- | ---------------- | -------------------- |
| preStart  | preStart + 1     | preStart + 1 + N + 1 |
| preEnd    | preStart + 1 + N | preEnd               |
| postStart | postStart        | postStart + N + 1    |
| postEnd   | postStart + N    | postEnd - 1          |

### Code

```java
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int[] pre;
    int[] post;
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.pre = pre;
        this.post = post;
        int len = post.length;
        for (int i = 0; i < len; i++) {
            map.put(post[i], i);
        }

        return helper(0, len - 1, 0, len - 1);
    }

    private TreeNode helper(int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) {
            return null;
        }

        TreeNode root = new TreeNode(pre[preStart]);

        if (preStart < preEnd) {
            int N = map.get(pre[preStart + 1]) - postStart;
            root.left  = helper(preStart + 1, preStart + 1 + N, postStart, postStart + N);
            root.right = helper(preStart + 1 + N + 1, preEnd, postStart + N + 1, postEnd - 1);
        }

        return root;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luj.gitbook.io/code/tree/7-serialize-and-deserialize/construct-binary-tree-from-traversals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.