# Tree - 102. Binary Tree Level Order Traversal

102. 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]
]
``````

go：

``````/**

* Definition for a binary tree node.

* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
/*// bfs recursive
func levelOrder(root *TreeNode) [][]int {
var res [][]int
if root == nil { return res }

traversalNode(root, &res, 0)

return res
}

func traversalNode(node * TreeNode, res *[][]int, h int) {
if node == nil { return }
if len(*res) < h + 1 {
*res = append(*res, []int{})
}

(*res)[h] = append((*res)[h], node.Val)
traversalNode(node.Left, res, h+1)
traversalNode(node.Right, res, h+1)
}*/

// bfs iterative
func levelOrder(root *TreeNode) [][]int {
var res [][]int
if root == nil {
return res
}
queue := []*TreeNode{root}

for len(queue) != 0 {
var temp  []int
var nextQ []*TreeNode

for len(queue) != 0 {
cur := queue[0]
queue = queue[1:]
temp = append(temp, cur.Val)
if cur.Left != nil {
nextQ = append(nextQ,cur.Left)
}

if cur.Right != nil {
nextQ = append(nextQ,cur.Right)
}
}

res = append(res, temp)
queue = append(queue, nextQ...)
}

return res
}
``````

Nothing just happens, it's all part of a plan.