106.Construct Binary Tree from Inorder and Postorder Traversal === ###### tags: `Medium`,`Tree`,`Array`,`Hash Table`,`Divide and Conquer` [106. Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) ### 題目描述 Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return *the binary tree*. ### 範例 **Example 1:** ![](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg) ``` Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7] ``` **Example 2:** ``` Input: inorder = [-1], postorder = [-1] Output: [-1] ``` **Constraints**: * 1 <= `inorder.length` <= 3000 * `postorder.length` == `inorder.length` * -3000 <= `inorder[i]`, `postorder[i]` <= 3000 * `inorder` and `postorder` consist of **unique** values. * Each value of `postorder` also appears in `inorder`. * `inorder` is **guaranteed** to be the inorder traversal of the tree. * `postorder` is **guaranteed** to be the postorder traversal of the tree. ### 解答 #### Python ```python class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: idx_map = {val:idx for idx, val in enumerate(inorder)} def recur(low, high): if low > high: return idx = idx_map[postorder.pop()] root = TreeNode(inorder[idx]) root.right = recur(idx + 1, high) root.left = recur(low, idx - 1) return root return recur(0, len(inorder) - 1) ``` > [name=Ron Chen][time= Thu, Mar 16, 2023] #### Javascript ```javascript= function buildTree(inorder, postorder) { const root = postorder[postorder.length - 1]; const rootIndex = inorder.indexOf(root); const leftInorder = inorder.slice(0, rootIndex); const rightInorder = inorder.slice(rootIndex + 1); const leftPostorder = postorder.slice(0, leftInorder.length); const rightPostorder = postorder.slice(leftInorder.length, postorder.length - 1); const tree = new TreeNode(root); if (leftInorder.length > 0) { tree.left = buildTree(leftInorder, leftPostorder); } if (rightInorder.length > 0) { tree.right = buildTree(rightInorder, rightPostorder); } return tree; } ``` > [name=Marsgoat][time=Mar 17, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)