刷題日記(15)Construct Binary Tree from Inorder and Postorder Traversal
Jan 19, 2021
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
解題思路:
- 利用inorder和postorder的順序來解題,先找到postorder的最後一位為root然後利用搜尋值在inoder中找到對應的位置,這樣就可以確定inorder分界點在哪了(左->中->右)
- 然後每次的遞迴就把inorder和postorder的左子樹們一起遞迴,以及右子樹們一起遞迴
- 每一次的遞迴都會產生一個root node,返回時會接到上一層的right或left
- 這樣完成遞迴時,樹也建置完成了
(mainfunction)
- 得到postorder的長度assign 給n
- 如果n是0,return null(代表已經到底或是傳進來的本來就是空的)
- 因為postorder的順序是左右中,所以最後一個一定是root,所以利用postorder[n-1]得到 root 的value
- 然後在inorder之中用for loop找到上面value所在位置,因為inorder的順序是左中右,利用中間的root分割了左右邊,所以找到root的位置就可以確定左右子樹了
- 接著新增一個left_inorder和left_postorder的int一維陣列,長度為index (因為兩個order起始都是左子樹)
- 開始for loop迴圈把inorder i小於index位置的值裝到left_inorder,以及把postorder i小於index位置的值裝到left_postorder裡
- 再接著新增一個right_inorder和right_postorder的一維陣列,right_inorder的長度為n-index-1,n為原本元素長度然後減掉左子樹和root。另外right_postorder的長度也一樣
- 之後開始for loop,i的起始值為index加1,因為inorder的root是在中間的,index的右邊開始才是右子樹,然後開始把inorder的右子樹們依序放進right_inorder的[i- index- 1]裡,因為共用i的關係,所以才會是i- index- 1
- 之後的另一個for loop,i的起始值為為index,因為在postorder裡,中間沒有root卡住,所以直接index即可(為右子樹)的第一個位置,然後iterate把值放進 right_postorder[i-index]裡,這邊的i-index也是因為共用i的關係,必須復原初始值為0
- 最後開始遞迴放入剛剛的左子樹的inorder和postorder,然後拿一個root.left接住
- 開始另一個遞迴放入剛剛的右子樹的inorder和postorder,然後拿一個root.right接住
- 最後回傳root,(每一次遞迴都會在第三行產生一個新的root node),然後因10和11的遞迴,就把left和right接上,這樣子樹就構造完成了




