🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem involves reconstructing a binary tree given its inorder and postorder traversal arrays. My initial thought is to leverage the properties of
---
![1000081264.png](https://assets.leetcode.com/users/images/242aba87-2152-405e-8b50-1bf9ffb4b0f0_1738594767.7733252.png)

---

## Intuition
The problem involves reconstructing a binary tree given its inorder and postorder traversal arrays. My initial thought is to leverage the properties of these traversals:
- Inorder traversal visits nodes in the order of left subtree, root, and then right subtree.
- Postorder traversal visits nodes in the order of left subtree, right subtree, and then root.

From the postorder array, we know that the last element is the root of the tree. Using this information, we can find the root's index in the inorder array to determine which elements belong to the left and right subtrees.

## Approach
1. **Mapping Indices**:
   - Create a map (`rec`) to store the indices of elements in the inorder array for quick lookups. This will help us efficiently find the position of any value in the inorder array.

2. **Recursive Helper Function**:
   - Implement a recursive function (`helper`) that takes parameters for the current ranges in both inorder and postorder arrays.
   - Base case: If the start index exceeds the end index for either array, return null (indicating no subtree).

3. **Constructing Nodes**:
   - In each recursive call:
     - Identify the root value from the last element of the current postorder range.
     - Create a new `TreeNode` for this root.
     - Find the index of this root value in the inorder array using the map.
     - Calculate the size of the left subtree based on this index.
     - Recursively call `helper` for both left and right subtrees using updated ranges.

4. **Return Result**:
   - The main function (`buildTree`) initializes everything and calls `helper` to construct and return the entire tree.

### Code Examples


```cpp []
#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> rec;
        for (int i = 0; i < inorder.size(); i++) {
            rec[inorder[i]] = i;
        }
        return helper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, rec);
    }

    TreeNode* helper(vector<int>& inorder, vector<int>& postorder,
                     int inStart, int inEnd,
                     int postStart, int postEnd,
                     unordered_map<int, int>& rec) {
        if (inStart > inEnd || postStart > postEnd) return nullptr;

        int val = postorder[postEnd];
        TreeNode* root = new TreeNode(val);
        int idx = rec[val];
        int leftSubtreeSize = idx - inStart;

        root->left = helper(inorder, postorder,
                             inStart, idx - 1,
                             postStart, postStart + leftSubtreeSize - 1,
                             rec);

        root->right = helper(inorder, postorder,
                              idx + 1, inEnd,
                              postStart + leftSubtreeSize, postEnd - 1,
                              rec);

        return root;
    }
};
```


```java []
import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> rec = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            rec.put(inorder[i], i);
        }
        return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, rec);
    }

    private TreeNode helper(int[] inorder, int[] postorder,
                            int inStart, int inEnd,
                            int postStart, int postEnd,
                            HashMap<Integer, Integer> rec) {
        if (inStart > inEnd || postStart > postEnd) return null;

        int val = postorder[postEnd];
        TreeNode root = new TreeNode(val);
        int idx = rec.get(val);
        int leftSubtreeSize = idx - inStart;

        root.left = helper(inorder, postorder,
                            inStart, idx - 1,
                            postStart, postStart + leftSubtreeSize - 1,
                            rec);

        root.right = helper(inorder, postorder,
                             idx + 1, inEnd,
                             postStart + leftSubtreeSize, postEnd - 1,
                             rec);

        return root;
    }
}
```


```javascript []
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    buildTree(inorder, postorder) {
        const rec = new Map();
        
        for (let i = 0; i < inorder.length; i++) {
            rec.set(inorder[i], i);
        }

        return this.helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, rec);
    }

    helper(inorder, postorder, inStart, inEnd, postStart, postEnd, rec) {
        if (inStart > inEnd || postStart > postEnd) return null;

        const val = postorder[postEnd];
        const root = new TreeNode(val);
        const idx = rec.get(val);
        const leftSubtreeSize = idx - inStart;

        root.left = this.helper(inorder, postorder,
                                inStart, idx - 1,
                                postStart, postStart + leftSubtreeSize - 1,
                                rec);

        root.right = this.helper(inorder, postorder,
                                 idx + 1, inEnd,
                                 postStart + leftSubtreeSize, postEnd - 1,
                                 rec);

        return root;
    }
}
```


```python []
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        rec = {val: i for i, val in enumerate(inorder)}
        
       # Helper function 
       def helper(in_start: int ,in_end: int ,post_start: int ,post_end: int):
           if in_start > in_end or post_start > post_end:
               return None

           val = postorder[post_end]
           root = TreeNode(val)
           idx = rec[val]
           left_subtree_size = idx - in_start

           # Recursively build left and right subtrees 
           root.left=helper(in_start ,idx-1 ,post_start ,post_start+left_subtree_size-1)
           root.right=helper(idx+1 ,in_end ,post_start+left_subtree_size ,post_end-1)

           return root

       return helper(0,len(inorder)-1 ,0,len(postorder)-1)
```


```dart []
class TreeNode {
  int val;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.val);
}

class Solution {
  
   TreeNode? buildTree(List<int> inorder,List<int>postOrder){
     final Map<int,int>rec={};
     for(int i= ;i<inOrder.length;i++){
       rec[inOrder[i]]=i; 
     }

     // Helper function 
     return helper(inOrder ,postOrder ,0 ,inOrder.length-(-),0 ,postOrder.length-(-),rec);
   }

   TreeNode? helper(List<int>inOrder,List<int>postOrder,int inStart,int inEnd,int posStart,int posEnd ,Map<int,int>rec){
     if(inStart>inEnd||posStart>posEnd)return null;

     final val=postOrder[posEnd]; 
     final root=TreeNode(val); 
     final idx=rec[val]!;
     final leftSubtreeSize=idx-inStart;

     // Recursively build left and right subtrees 
     root.left=helper(inOrder ,postOrder,inStart ,idx-(-),posStart,posStart+leftSubtreeSize-(-),rec); 
     root.right=helper(inOrder ,postOrder ,idx+(-) ,inEnd,posStart+leftSubtreeSize,posEnd-(-),rec);

     return root; 
   }
}
```

## Complexity
- **Time complexity**: $$O(n)$$ where $$n$$ is the number of nodes in the binary tree. Each node is processed once during DFS traversal and once during mapping indices.

- **Space complexity**: $$O(n)$$ due to storing indices of elements from `inorder` traversal and recursion stack space used during DFS.

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Hash Table', 'Divide and Conquer', 'Tree', 'C', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']