刷題日記（12）Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

— — — — —— -(解法1, BFS with 1 queue) — —— — — -

解題思路：

1. 紀錄queue的size很重要，他決定了level結束加進reult的時間
2. 需要一個ArrayList result紀錄結果，需要一個ArrayList level紀錄每一層的node的 val，需要一個int 叫size紀錄queue的size，一個head 去接住每次queue poll 出來的值
3. 這題Invert Binary Tree的第二種解法有點像，但多了一個for loop(queue.size)

(main function)

1. 新增一個空的result ArrayList
2. Base case 如果傳進來root為空，則return 剛剛新增的result ArrayList
3. 新增一個Queue<TreeNode>類型的LinkedList
4. 把傳進來的root放到queue裡
5. while(queue不為空時)，新增一個空的ArrayList<Integer>叫level

5.1 然後記錄一下這個queue的size

5.2 開始for loop(小於queue的size就繼續跑)

5.2.1 新增一個head標籤得到queue poll出來的node

5.2.2 然後把head的val值放到level裡

5.2.3 如果head的左邊不為空，把head的左邊offer進queue裡

5.2.4 如果 head的右邊不為空，把head的右邊offer進queue裡

5.3 for loop結束一次，代表一層跑完了，把level這個list加進result

5.4 如果queue還沒空就繼續5的while迴圈

5.5如果queue已經空了代表node都已經遍歷過一次，回傳result這個list極為答案

以這個為範例