Contents

# 106. 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 :

Note

Example 1:

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]

#### 解題思路 :

• 這個也是一個非常經典的題目! 題目給你兩組數組，分別是inorder排序與postorder排序，需要用兩個數組的特性去建構出linked node版本的binary tree
• inorder的特性是left -> mid -> right
• postorder的特性是 left -> right -> mid
• 由於以上兩種特性我可以做以下操作:
1. 先取得postorder數組的最後一個element，他必定是mid(root)
2. 再用該element去inorder中尋找，這樣就能依照inorder的規則去判斷左邊是Left tree 右邊是 right tree，將其與選出的root連接
3. 重複以上動作

### Recursive解法

• time complexity: O(n^2) , space complexity: O(n)

Runtime: 4 ms, faster than 90.98% of Go online submissions for Construct Binary Tree from Inorder and Postorder Traversal.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func buildTree(inorder []int, postorder []int) *TreeNode { if len(inorder) == 0 || len(postorder) == 0 { return nil midVal := postorder[len(postorder)-1] midIndex := findIndex(midVal,inorder) node := &TreeNode { Val: midVal, Left: buildTree(inorder[:midIndex], postorder[:midIndex]), Right: buildTree(inorder[midIndex+1:], postorder[midIndex:len(postorder)-1]), } return node } func findIndex(tar int, arr []int) (index int) { for i, v := range arr { if v == tar { return i } } return -1 } ``````