105. Construct Binary Tree from Preorder and Inorder Traversal.md

105. Construct Binary Tree from Preorder and Inorder Traversal

---

Difficulty : Medium

Related Topics : Tree、Array、DFS

---

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

Note:

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

Solution

• mine
  • Java
    • Runtime: 3 ms, faster than 67.96%, Memory Usage: 42.1 MB, less than 5.08% of Java online submissions

      //O(N)time
      //O(N)space
      int[] pre, in;
      HashMap<Integer, Integer> map;
      int rootIndex;
      public TreeNode buildTree(int[] preorder, int[] inorder) {
          pre = preorder;
          in = inorder;
          int n = in.length;
          map = new HashMap<>();
          for(int i = 0; i < n; i++){
              map.put(in[i], i);
          }
          rootIndex = 0;
          return helper(0, n - 1);
      }
      
      TreeNode helper(int l, int r){
          if(l > r)  return null;
      
          int t = pre[rootIndex];
          rootIndex++;
          TreeNode node = new TreeNode(t);
          int mid = map.get(t);
          node.left = helper(l, mid - 1);
          node.right = helper(mid + 1, r);
          return node;
      }
      

---