0102. 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]
]

``````

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 BFS
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
queue := []*TreeNode{root}
res := make([][]int, 0)
for len(queue) > 0 {
l := len(queue)
tmp := make([]int, 0, l)
for i := 0; i < l; i++ {
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
tmp = append(tmp, queue[i].Val)
}
queue = queue[l:]
res = append(res, tmp)
}
return res
}

// 解法二 DFS
func levelOrder1(root *TreeNode) [][]int {
var res [][]int
var dfsLevel func(node *TreeNode, level int)
dfsLevel = func(node *TreeNode, level int) {
if node == nil {
return
}
if len(res) == level {
res = append(res, []int{node.Val})
} else {
res[level] = append(res[level], node.Val)
}
dfsLevel(node.Left, level+1)
dfsLevel(node.Right, level+1)
}
dfsLevel(root, 0)
return res
}

``````

Apr 8, 2023
Edit this page