---
# System prepended metadata

title: Leetcode 105. Construct Binary Tree Form Preorder And Inorder Traversal
tags: [Binary Tree, Tree, DFS, Leetcode, Stack]

---

# 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)
