# 106 Construct Binary Tree from Inorder and Postorder Traversal

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

## 1. Question

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

## 2. Implementation

**(1) Recursion**

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

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return constructTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    public TreeNode constructTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);

        int index = map.get(root.val);

        root.left = constructTree(postorder, postStart, postStart + (index - inStart) - 1, inorder, inStart, index - 1, map);
        root.right = constructTree(postorder, postStart + (index - inStart), postEnd - 1, inorder, index + 1, inEnd, map);
        return root;
    }
}
```

## 3. Time & Space Complexity

Recursion: 时间复杂度O(n^2)，如果tree是skewed, 当tree是balanced，时间复杂度是O(nlogn)，空间复杂度是O(n)，因为map


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/tree/106-construct-binary-tree-from-inorder-and-postorder-traversal.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.