Binary Tree Level Order Traversal

Given the rootof a binary tree, return the level order traversal of its nodes' values
. (i.e., from left to right, level by level).

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

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

解析

題目給定一個二元樹根結點 root。

要求實作一個演算法根據 level order 來尋訪二元樹，並回傳每個 level的結構

這題跟 199. Binary Tree Right Side View 一樣需要用 Breadth First Search 演算法來實作

使用一個 queue 來儲存每個 level 的所有 node

每次都把這個 queue 的 level 紀錄下來及為所求

如下圖

這樣等到 queue 為空時，整個tree 都走訪結束

因此時間複雜度是 O(n) ，空間複雜度也是 O(n)

程式碼

package sol

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	result := [][]int{}
	queue := []*TreeNode{root}
	for len(queue) != 0 {
		qLen := len(queue)
		level := []int{}
		for idx := 0; idx < qLen; idx++ {
			node := queue[0]
			queue = queue[1:]
			if node != nil {
				level = append(level, node.Val)
				queue = append(queue, node.Left, node.Right)
			}
		}
		if len(level) != 0 {
			result = append(result, level)
		}
	}
	return result
}

困難點

1. 理解二元樹 level order traversal的意思
2. 理解怎麼去做 level order traversal

Solve Point

• [x] Understand what problem would like to solve
• [x] Analysis Complexity