刷題日記(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) — —— — — -
解題思路:
- 紀錄queue的size很重要,他決定了level結束加進reult的時間
- 需要一個ArrayList result紀錄結果,需要一個ArrayList level紀錄每一層的node的 val,需要一個int 叫size紀錄queue的size,一個head 去接住每次queue poll 出來的值
- 這題Invert Binary Tree的第二種解法有點像,但多了一個for loop(queue.size)
(main function)
- 新增一個空的result ArrayList
- Base case 如果傳進來root為空,則return 剛剛新增的result ArrayList
- 新增一個Queue<TreeNode>類型的LinkedList
- 把傳進來的root放到queue裡
- 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極為答案





