[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal

轉自LeetCode

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

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

<Solution>

這題和 Construct Binary Tree from Preorder and Inorder Traversal 類似

只是改成 postorder 和 inorder

思考方式也是一樣，可以用 recursive 來解

• 因為是 postorder (left -> right -> root)，所以由後往前看

• 在 inorder 裡面找到對應的值，左邊的數就在左子樹，右邊的數就在右子樹

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

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

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

詳細說明可以參考 Construct Binary Tree from Preorder and Inorder Traversal

code 如下

和 Construct Binary Tree from Preorder and Inorder Traversal 一樣，當然也有更快的 iterative 的解法

因為換成 postorder，所以由後往前找，並且先看 right child 再看 left child

其餘的想法都是一樣

code 如下