# [LeetCode] Construct Binary Tree from Preorder and Inorder Traversal [LeetCode] Construct Bina

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

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

```/**
* 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[] preorder, int[] inorder) {
Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
for(int i=0; i<inorder.length; i++)
inorderMap.put(inorder[i],i);
return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inorderMap);
}

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

cur.left = buildTree(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1, inorderMap);
cur.right = buildTree(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight, inorderMap);
return cur;
}
}```

0 条评论

## 相关文章

14820

19420

26240

### ZooKeeper典型应用场景一览（转）

ZooKeeper是一个高可用的分布式数据管理与系统协调框架。基于对Paxos算法的实现，使该框架保证了分布式环境中数据的强一致性，也正是基于这样的特性，使得Z...

12310

12320

60720

16930

1.5K30

15050

18420