刷題日記(12)Binary Tree Level Order Traversal

Rachel Yeh
Jan 5, 2021

--

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極為答案

以這個為範例

--

--

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet