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

106. Construct Binary Tree from Inorder and Postorder Traversal

---

leetcode Daily Challenge on July 27th, 2020.

leetcode-cn Daily Challenge on September 25th, 2020.

---

Difficulty : Medium

Related Topics : Tree、Array、DFS

---

Given inorder and postorder 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: 2 ms, faster than 77.11%, Memory Usage: 42 MB, less than 5.51% of Java online submissions

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

---