# [LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

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

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

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

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
for(int i=0; i<inorder.length; i++)
inorderMap.put(inorder[i],i);
return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, inorderMap);

}

public TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight, Map<Integer, Integer> inorderMap){
if(iLeft>iRight || pLeft>pRight)
return null;
TreeNode cur = new TreeNode(postorder[pRight]);
//int i = 0;
//for(i=iLeft; i<=iRight; i++)
//   if(postorder[pRight]==inorder[i])
//        break;
int i = inorderMap.get(postorder[pRight]);
cur.left = buildTree(inorder, iLeft, i-1, postorder, pLeft, pLeft+i-iLeft-1, inorderMap);
cur.right = buildTree(inorder, i+1, iRight, postorder, pLeft+i-iLeft, pRight-1, inorderMap);
return cur;
}
}```

0 条评论

## 相关文章

9010

9220

59520

12620

10920

23920

9510

97130

23550

### 《剑指Offer》50道算法面试题

《剑指Offer》50道算法面试题 - C++版，本来一开始想用Java来写，不过看看了，JDK里封装了很多算法，用Java写就没意思了，于是用选择了C++，顺...

1.9K20