[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal

轉自 LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

<Solution>

這題要我們從 preorder 和 inorder traversal 兩個資訊中，把 binary tree 給重建出來

這邊先注意到題目有說，不會有重複的元素

因為有這個前題條件，我們可以找出 preorder traversal 中的某個值，在 inorder traversal 中的位置

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

preorder : [1, 2, 6, 9, 7, 8]

inorder : [6, 2, 9, 1, 7, 8]

因為 preorder 的特性，preorder[0] = 1 一定是 root

找出 1 在 inorder 的位置，index = 4，inorder[4] = 1

那麼，inorder[0] 到 inorder[3] 一定是在 inorder[4] 的左子樹

inorder[5] 到 inorder[6] 一定是在 inorder[4] 的右子樹

因此，可以每次都以 preorder 的第一個元素當 root，然後 recursive 的找出左子樹和右子樹

那當找左右子樹的時候，preorder 的範圍變化會如下

找左子樹時:

preorder[0] 會是當下的 root

preorder : [1, 2, 6, 9, 7, 8]
inorder : [6, 2, 9, 1, 7, 8]

preorder 不需要再看 index 0，只看 index 1 到 index 5

將 preorder[1-5] 繼續 recursive 下去

preorder : [2, 6, 9, 7, 8]
inorder : [6, 2, 9, 3, 7, 8]

找右子樹時:

preorder[0] 會是當下的 root

preorder : [1, 2, 6, 9, 7, 8]
inorder : [6, 2, 9, 1, 7, 8]

而這時候，inorder[0-2] 這三個數都是左子樹的元素，且都已經處理完了

所以接下來要看的地方是 inorder[4-5]

這也代表在 preorder 中，從 preorder[0] 往右數 3 個 (inorder[0-2]) 都是處理過的數

所以 preorder 的搜尋範圍起始點就會變成 preorderRootIndex + (inorderRootIndex - inorderStart) + 1 = 0 + (3 - 0) + 1 = 4

也就是從 preorder[4] 開始就會是在右子樹的元素

code 如下(參考資料)

這題還有 iterative 的解法

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

preorder : [1, 2, 6, 9, 7, 8]

inorder : [6, 2, 9, 1, 7, 8]

觀念一樣，preorder[0] = 1 一定是 root，所以 inorder[0-2]一定是 root 的左子樹的node

而 inorder[0] = 6，這一定是最左邊的 node

因此，當目前 preorder 的值不等於 inorder[0] 之前，就是一路向左連接下去

     1
    /
   2
  /
 6

preorder : [1, 2, 6, 9, 7, 8]

inorder : [6, 2, 9, 1, 7, 8]

當 preorder[2] = 6 = inorder[0] 的時候，代表目前所有的 left child 都已經處理完了

接下來就要回推到第一個有 right child 的 node

因為要回推，所以在過程當中，使用 stack 將之前的 node 都儲存起來

此實，stack 裡面有 [1, 2, 6]

因為 inorder 的特性，如果有 right child 的 node，其 right child 一定會夾在當前 node 和它的 parent 之間

就像是例子中的 9 : inorder : [6, 2, 9, 1, 7, 8]

因此，只要檢查 stack 裡面的 top，是不是和當前 inorder 的值一樣

是的話，就 pop 出來，然後用一個 tmpNode 指到它，並且將 inorder 的 index 指到下一個

所以會變成

     1
    /
   2
  / \
 6   9

tmpNode = 2

preorder : [1, 2, 6, 9, 7, 8]

inorder : [6, 2, 9, 1, 7, 8]

這時候把 9 變成 2 的 right child，並且再把 9 丟到 stack 就可以了

stack = [1,9]

然後再重複之前的步驟，直到歷遍完 preorder

code 如下 (參考資料)