刷題日記（15）Construct Binary Tree from Inorder and Postorder Traversal

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

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

解題思路：

1. 利用inorder和postorder的順序來解題，先找到postorder的最後一位為root然後利用搜尋值在inoder中找到對應的位置，這樣就可以確定inorder分界點在哪了（左->中->右）
2. 然後每次的遞迴就把inorder和postorder的左子樹們一起遞迴，以及右子樹們一起遞迴
3. 每一次的遞迴都會產生一個root node，返回時會接到上一層的right或left
4. 這樣完成遞迴時，樹也建置完成了

（mainfunction）

1. 得到postorder的長度assign 給n
2. 如果n是0，return null(代表已經到底或是傳進來的本來就是空的)
3. 因為postorder的順序是左右中，所以最後一個一定是root，所以利用postorder[n-1]得到 root 的value
4. 然後在inorder之中用for loop找到上面value所在位置，因為inorder的順序是左中右，利用中間的root分割了左右邊，所以找到root的位置就可以確定左右子樹了
5. 接著新增一個left_inorder和left_postorder的int一維陣列，長度為index （因為兩個order起始都是左子樹）
6. 開始for loop迴圈把inorder i小於index位置的值裝到left_inorder，以及把postorder i小於index位置的值裝到left_postorder裡
7. 再接著新增一個right_inorder和right_postorder的一維陣列，right_inorder的長度為n-index-1，n為原本元素長度然後減掉左子樹和root。另外right_postorder的長度也一樣
8. 之後開始for loop，i的起始值為index加1，因為inorder的root是在中間的，index的右邊開始才是右子樹，然後開始把inorder的右子樹們依序放進right_inorder的[i- index- 1]裡，因為共用i的關係，所以才會是i- index- 1
9. 之後的另一個for loop，i的起始值為為index，因為在postorder裡，中間沒有root卡住，所以直接index即可（為右子樹）的第一個位置，然後iterate把值放進 right_postorder[i-index]裡，這邊的i-index也是因為共用i的關係，必須復原初始值為0
10. 最後開始遞迴放入剛剛的左子樹的inorder和postorder，然後拿一個root.left接住
11. 開始另一個遞迴放入剛剛的右子樹的inorder和postorder，然後拿一個root.right接住
12. 最後回傳root，(每一次遞迴都會在第三行產生一個新的root node)，然後因10和11的遞迴，就把left和right接上，這樣子樹就構造完成了