###### tags: `107 Binary Tree Level Order Traversal II`
# 107 Binary Tree Level Order Traversal II 筆記

## 題目：Given the root of a binary tree, return *the bottom-up level order traversal of its nodes' values*
. (i.e., from left to right, level by level from leaf to root).

**Constraints:**

- The number of nodes in the tree is in the range `[0, 2000]`.
- `1000 <= Node.val <= 1000`

先搞懂題目的意思才能開始解題

### 找了一下資料發現原來 Binary Trhttps://hackmd.io/PoY2WlQwQ_2M2hxSpNOfjg?both#ee Traversal 有好幾種，分別有：

- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
- Level-order Traversal **(這個就是題目要用的方法)**

### 範例

flowchart TB
    Root((1))
    Root --- Node1
    Node1((2))
    Root --- Leaf3
    Leaf3((3))
    Node1 --- Leaf1
    Leaf1((4))
    Node1 --- Leaf2
    Leaf2((5))

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

`[1, 2, 4, 5, 3]`

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

`[4, 2, 5, 1, 3]`

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

`[4, 5, 2, 3, 1]`

4. Level-order Traversal: 順序會是從根節點一層一層往下，由左而右

`[1, 2, 3, 4, 5]`

---

## 思路

知道題目意思後就比較好解了，他是一層一層往下但又有點不一樣，他是從最下面那層開始的，那其實還是可以把他從上到下先記錄起來後再翻轉順序就好了。

從 root 開始就把它記錄在 output: [[Int]] 裡面，往下找的時候就順便紀錄 Level 當作 Index 來使用，他是從左而右所以找的時候要從左邊開始，遇到就紀錄在 output 裡面，這樣歷遍完後就會是正常的 Lever-order Traversal，然後再 reverse output 就好了。

## Level Order Traversal

func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
        var queue: [TreeNode?] = []
        var result: [[Int]] = []
        
        guard let root = root else { return [] }
        queue.append(root)
        traverse(queue: queue, result: &result)
        return result.reversed()
    }
    
    private func traverse(queue: [TreeNode?], result: inout [[Int]]) {
        var nextQueue: [TreeNode?] = []
        guard !queue.isEmpty else { return }
        result.append(queue.compactMap { $0?.value })
        for node in queue {
            guard let node = node else { continue }
            if let leftNode = node.left {
                nextQueue.append(leftNode)
            }
            if let rightNode = node.right {
                nextQueue.append(rightNode)
            }
        }
        traverse(queue: nextQueue, result: &result)
    }

## Inorder Traversal With HashTable

private func inOrderTraversal(root: TreeNode?, level: Int = 1, result: inout [Int: [Int]], depth: inout Int) {
    guard let root = root else { return }
    depth = max(level, depth-1)
    if let left = root.left {
        if result[level] == nil  {
            result[level] = [left.val]
        } else {
            result[level]?.append(left.val)
        }
        inOrderTraversal(root: left, level: level + 1, result: &result, depth: &depth)
    }
        
    if let right = root.right {
        if result[level] == nil  {
            result[level] = [right.val]
        } else {
            result[level]?.append(right.val)
        }
        inOrderTraversal(root: right, level: level + 1, result: &result, depth: &depth)
    }
}
    
func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }
    var levelDict: [Int: [Int]] = [0: [root.val]]
    var depth: Int = 0
        
    inOrderTraversal(root: root, result: &levelDict, depth: &depth)
        
    var result = [[Int]]()
    while depth >= 0 {
        result.append(levelDict[depth]!)
        depth -= 1
    }
    
    return result
}

---

## 心得

題目真的要先看清楚再開始思考怎麼做，不然很可能會白做工！一開始看 leetcode 給的範例，還以為是要把兩個兩個節點放在一個 array 裡面，了解題目後才發現原來是把同一層的放在一起的意思。

其實做題目的時候花最多時間的地方是在怎麼建立 Input ，因為我是先在 Playground 裡面做的，所以不會有 input 準備好給我測試，所以花了很多時間在建立 Binary Tree，反而解題用的時間比較短。

---
[作業](https://github.com/GametreeRoger/LeetCode/blob/main/LeetCode107.playground/Contents.swift)