tags: 106 Construct Binary Tree from Inorder and Postorder Traversal

106 Construct Binary Tree from Inorder and Postorder Traversal 筆記

題目：

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• 3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

先搞懂 inorder 和 postorder，之前寫 107 的時候就查過了

1. Inorder Traversal: 順序會是左子節點、根節點、右子節點

   [4, 2, 5, 1, 3]

2. Postorder Traversal: 順序會是左子節點、右子節點、根節點

   [4, 5, 2, 3, 1]

觀察：

可以觀察到 Postorder 都會把跟節點放到最後，前面就會是他的左邊和右邊的 subtree

而把 Postorder 找到的 root 放到 Inorder 裡面會看到他剛好把左邊後右邊的 subtree 分隔開來，而 Postorder 自己的左邊 subtree 會跟 Inorder 的 subtree 個數一樣，所以 Postorder 的前三個就是他的 subtree

Inorder: [4,2,5] [1] [3]

Postorder: [4,5,2] [3] [1]

左右邊的 subtree 都分出來後就可以再用同樣的規則繼續把樹完成

Inorder: [4, 2, 5]

Postorder: [4, 5, 2]

2 是 root 拿出來

Inorder: [4] [2] [5]

Postorder: [4] [5] [2]