# 106. Construct Binary Tree from Inorder and Postorder Traversal

{% embed url="<https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/>" %}

思路见Q105：

{% content-ref url="105.-construct-binary-tree-from-preorder-and-inorder-traversal" %}
[105.-construct-binary-tree-from-preorder-and-inorder-traversal](https://xuqiangwen1994.gitbook.io/practice/105.-construct-binary-tree-from-preorder-and-inorder-traversal)
{% endcontent-ref %}

这题的主要变化是：

1. 需要逆序遍历`postorder`（其实`逆序postorder`就是先搜right subtree的`preorder`）
2. 相应地，要先确定 rght subtree 再去确定 left

```python
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder: return None
        rootVal = postorder.pop()
        root = TreeNode(rootVal)
        idx = inorder.index(rootVal)
        
        root.right = self.buildTree(inorder[idx+1:], postorder)
        root.left = self.buildTree(inorder[:idx], postorder)
        
        return root
```
