刷題日記(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極為答案

以這個為範例

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response