106 Construct Binary Tree from Inorder and Postorder Traversal 筆記

###### 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 的時候就查過了 ```mermaid flowchart TB Root((1)) Root --- Node1 Node1((2)) Root --- Leaf3 Leaf3((3)) Node1 --- Leaf1 Leaf1((4)) Node1 --- Leaf2 Leaf2((5)) ``` 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] ```mermaid flowchart TB Root((1)) style Root color: green Root --- Node1 Node1((4,2,5)) style Node1 color: red Root --- Leaf3 Leaf3((3)) style Leaf3 color: orange ``` 左右邊的 subtree 都分出來後就可以再用同樣的規則繼續把樹完成 Inorder: [4, 2, 5] Postorder: [4, 5, 2] 2 是 root 拿出來 Inorder: [4] [2] [5] Postorder: [4] [5] [2] ```mermaid flowchart TB Root((1)) style Root color: green Root --- Node1 Node1((2)) style Node1 color: green Root --- Leaf3 Leaf3((3)) style Leaf3 color: orange Node1 --- Leaf1 Leaf1((4)) style Leaf1 color: red Node1 --- Leaf2 Leaf2((5)) style Leaf2 color: orange ```