# 72,73.Construct Binary Tree

## 72.Construct Binary Tree from Inorder and Postorder Traversal(Medium)

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

### Notice

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

**Example**

Given inorder`[1,2,3]`and postorder`[1,3,2]`, return a tree:

```
  2
 / \
1   3
```

## Code

<https://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html>

要知道如何构建二叉树，首先我们需要知道二叉树的几种遍历方式，譬如有如下的二叉树：

```
                1
        --------|-------
        2               3
    ----|----       ----|----
    4       5       6       7
```

* 前序遍历 1245367
* 中序遍历 4251637
* 后续遍历 4526731

具体到上面这一题，我们知道了一个二叉树的中序遍历以及后序遍历的结果，那么如何构建这颗二叉树呢？

仍然以上面那棵二叉树为例，我们可以发现，对于后序遍历来说，最后一个元素一定是根节点，也就是1。然后我们在中序遍历的结果里面找到1所在的位置，那么它的左半部分就是其左子树，有半部分就是其右子树。

我们将中序遍历左半部分425取出，同时发现后序遍历的结果也在相应的位置上面，只是顺序稍微不一样，也就是452。我们可以发现，后序遍历中的2就是该子树的根节点。

上面说到了左子树，对于右子树，我们取出637，同时发现后序遍历中对应的数据偏移了一格，并且顺序也不一样，为673。而3就是这颗右子树的根节点。

重复上述过程，通过后续遍历找到根节点，然后在中序遍历数据中根据根节点拆分成两个部分，同时将对应的后序遍历的数据也拆分成两个部分，重复递归，就可以得到整个二叉树了。

这里我们需要注意，为了保证快速的在中序遍历结果里面找到根节点，我们使用了hash map。

```
public HashMap<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || postorder.length == 0 || inorder == null || inorder.length == 0 ) {
            return null;
        }
        map=new HashMap<Integer,Integer>();
        for (int i = 0; i < inorder.length; ++i){
            map.put(inorder[i],i);
        }

        int right1 = inorder.length-1;
        int right2 = postorder.length-1;
        return build(inorder,0,right1,postorder,0,right2);

    }

    public TreeNode build(int[] inorder, int left1, int right1,
                          int[] postorder, int left2, int right2) {
            if (left1 > right1 || left2 > right2){
                return null;
            } 
            TreeNode root = new TreeNode(postorder[right2]);

            //get the index of current root in inorder array
            //new inorder-->(left1,mid-1) && (mid+1,right1)
            int mid = map.get(postorder[right2]);
            //用num记录下次遍历的数组的长度，好计算left和right
            int num = mid-left1;

            //dfs: 注意上面的范围
            root.left = build(inorder, left1, mid-1, postorder, left2, left2+num-1);
            root.right = build(inorder, mid+1, right1, postorder, left2+num, right2-1);

            return root;
    }
```

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

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

### Notice

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

**Example**

Given in-order`[1,2,3]`and pre-order`[2,1,3]`, return a tree:

```
  2
 / \
1   3
```

## Code

这题跟上面那题类似，通过前序遍历和中序遍历的结果构造二叉树，我们只需要知道前序遍历的第一个值就是根节点，那么仍然可以采用上面提到的方式处理：

* 通过前序遍历找到根节点
* 通过根节点将中序遍历数据拆分成两部分
* 对于各个部分重复上述操作

注意每次递归时index的计算

```
public HashMap<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0){
            return null;
        }
        map = new HashMap<Integer,Integer>();
        for (int i = 0; i< inorder.length; ++i) {
            map.put(inorder[i],i);
        }
        int right1 = preorder.length-1;
        int right2 = inorder.length-1;

        return build(preorder, 0, right1, inorder, 0, right2);
    }

    public TreeNode build (int[] preorder, int left1, int right1,
                           int[] inorder, int left2, int right2) {
            if (left1 > right1 || left2 > right2 ){
                return null;
            } 
        TreeNode root = new TreeNode(preorder[left1]);

        int mid = map.get(preorder[left1]);
        int num = mid-left2;

        root.left = build(preorder, left1+1, left1+num, inorder, left2,mid-1);
        root.right = build(preorder, left1+num+1, right1, inorder, mid+1, right2);

        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://junnie.gitbook.io/nine-chapter/2.binary-tree/7273construct-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.