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

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response