> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/tree/106-construct-binary-tree-from-inorder-and-postorder-traversal.md).

# 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