# Leetcode 105. Construct binary tree from preorder and inorder traversal ### Stack 解法 ```python= # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder: return None root = TreeNode(preorder[0]) stack = [root] inorderIndex = 0 for preorderIndex in range(1, len(preorder)): # preorderIndex 從 1 開始 preorderVal = preorder[preorderIndex] # 要加入的節點 node = stack[-1] # 棧頂節點 if node.val != inorder[inorderIndex]: # 棧頂節點不等於 inorder 節點，代表 inorder 節點為棧頂節點的左兒子 node.left = TreeNode(preorderVal) stack.append(node.left) else: while stack and stack[-1].val == inorder[inorderIndex]: # 如果棧頂節點和 inorder 節點一致，代表要加入的節點 (preorderVal) 會是棧中某個節點的右兒子，依序彈出棧中的值做比對，直到棧頂節點和 inorder 指向的節點不ㄧ致為止 (或者是棧中沒有節點，有可能是找到根節點)，即是找到父節點 node = stack.pop() # 要尋找的父節點 inorderIndex += 1 # 每彈出一個節點就要把 inorder 索引加一 node.right = TreeNode(preorderVal) # 把當前節點加入為父節點的右兒子 stack.append(node.right) # 推入棧中 return root ``` #### 核心邏輯 二元樹前序與中序遍歷的順序如下列所示 ``` preorder: [root,(left sub tree),(right sub tree)] inorder : [(reverse left sub tree),root,(reverse right sub tree)] ``` 使用 stack 來重建二元樹的根本邏輯就是，使用 inorder 來比對 preorder 是否已經走完了 left sub tree，也就是下列情況 ``` stack top ->| | <- preorderIndex (已經準備要重建 right sub tree 開始推出堆棧裡的節點並從 inorder 找出 root) preorder: [root,(left sub tree),(right sub tree)] inorder : [(reverse left sub tree),root,(reverse right sub tree)] | <- inorderIndex ``` 只要搞懂了加入左子樹和右子樹的時機，這一題就不這麼難了 #### 範例 ``` preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] ``` 1. 棧頂節點和 inorder 節點不一致，把 節點 9 加入 節點 3 的左兒子，並把 節點 9 加入棧中 ```python= stack = [3] preorderIndex = 1 inorderIndex = 0 preorder[preorderIndex] => 9 # 欲加入節點 stack[-1] => 3 # 棧頂節點 inorder[inorderIndex] => 9 # inorder節點 ``` 2. 棧中節點和 inorder 節點一致，代表棧中 有一個節點 是 當前欲加入節點 的父節點，並且 當前欲加入節點為那個父節點的右兒子，依序彈出棧中節點，並且遞增 inorderIndex，直到找出欲加入節點的父節點為止 - 依序彈出棧中節點 9,3 ，並且遞增 inorderIndex 2 次，棧中最後沒有節點了，代表最後一個彈出的節點 3 為 當前欲加入節點 20 的父節點 - 把 20 加入 3 的 右兒子 - 把 20 推入棧中 ```python= stack = [3,9] preorderIndex = 2 inorderIndex = 0 preorder[preorderIndex] => 20 # 欲加入節點 stack[-1] => 9 # 棧頂節點 inorder[inorderIndex] => 9 # inorder節點 ``` 3. 棧頂節點和 inorder 節點不一致，把 節點 15 加入 節點 20 的左兒子，並把 節點 15 加入棧中 ```python= stack = [20] preorderIndex = 3 inorderIndex = 2 preorder[preorderIndex] => 15 # 欲加入節點 stack[-1] => 20 # 棧頂節點 inorder[inorderIndex] => 15 # inorder節點 ``` 4. 棧中節點和 inorder 節點一致，代表棧中 有一個節點 是 當前欲加入節點 的父節點，並且 當前欲加入節點為那個父節點的右兒子，依序彈出棧中節點，並且遞增 inorderIndex，直到找出欲加入節點的父節點為止 - 依序彈出棧中節點 20,15 ，並且遞增 inorderIndex 2 次，棧中最後沒有節點了，代表最後一個彈出的節點 20 為 當前欲加入節點 7 的父節點 - 把 7 加入 20 的 右兒子 - 把 7 推入棧中 ```python= stack = [20,15] preorderIndex = 4 inorderIndex = 2 preorder[preorderIndex] => 7 # 欲加入節點 stack[-1] => 15 # 棧頂節點 inorder[inorderIndex] => 15 # inorder節點 ``` 5. 完成二叉樹還原全過程 ![](https://hackmd.io/_uploads/BJO2QgTYh.png)