# Construct Binary Tree

## 105. Construct Binary Tree from Preorder and Inorder Traversal

```java
 public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0) return null;

    int num = preorder[0];
    int len = 0;
    for(int i=0; i<inorder.length; i++){
        if(inorder[i] == num)
            len = i;
    }

    TreeNode node = new TreeNode(num);
    node.left = buildTree(Arrays.copyOfRange(preorder, 1, 1+len),
                         Arrays.copyOfRange(inorder, 0, len));
    node.right = buildTree(Arrays.copyOfRange(preorder, 1+len, preorder.length),
                        Arrays.copyOfRange(inorder, 1+len, inorder.length));
    return node;
}
```

## 106. Construct Binary Tree from Inorder and Postorder Traversal

```java
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(postorder.length == 0) return null;

    int n = postorder[postorder.length-1];
    int len = 0;
    for(int i=0; i<inorder.length; i++){
        if(inorder[i] == n) len = i;
    }

    TreeNode root = new TreeNode(n);
    root.left = buildTree(Arrays.copyOfRange(inorder, 0, len), 
                          Arrays.copyOfRange(postorder, 0, len));
    root.right = buildTree(Arrays.copyOfRange(inorder, len+1, inorder.length),
                           Arrays.copyOfRange(postorder, len, postorder.length-1));
    return root;
}
```

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

Return any binary tree that matches the given preorder and postorder traversals.

Example

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]

* find the length of left tree and use it split the left tree and right tree
* Preorder and postorder left tree length are the same, and pre\[1] the head of left tree, use is to find the last position in postorder

```java
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    // pre  [1][2,4,5][3,6,7]
    // post [4,5,2][6,7,3][1]

    int len = pre.length;
    if(len == 0) return null;
    TreeNode node = new TreeNode(pre[0]);
    if(len == 1) return node;

    // find out the length of left tree
    int left_len = 0;
    for(int i=0; i<len; i++){
        if(post[i] == pre[1]) left_len = i+1;
    }

    node.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1+left_len), 
                                        Arrays.copyOfRange(post, 0, left_len));
    node.right = constructFromPrePost(Arrays.copyOfRange(pre, 1+left_len, len),
                                         Arrays.copyOfRange(post, left_len, len-1));
    return node;
}
```


---

# 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://netjimmy.gitbook.io/code-interview-note/binary_tree/construct-binary-tree.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.