刷題日記(15)Construct Binary Tree from Inorder and Postorder Traversal

Rachel Yeh
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

解題思路:

  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接上,這樣子樹就構造完成了

--

--

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet