前言
持续更新了
正文
问题来源
本问题来自leetcode上的429题。
最近工作压力有点大，早上起来做道题解解压。
问题描述
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1:
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
分析：
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) [][]int {
if root == nil {
return nil
}
queue := []*Node{root}
next := []*Node{}
ret := [][]int{}
row := []int{}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
row = append(row, cur.Val)
for i := 0; i < len(cur.Children); i++ {
next = append(next, cur.Children[i])
}
if len(queue) == 0 {
queue = next
next = []*Node{}
ret = append(ret, row)
row = []int{}
}
}
return ret
}
别人的做法
func levelOrder(root *Node) [][]int {
if root == nil {
return [][]int{}
}
queue := []*Node{}
queue = append(queue,root)
ans := [][]int{}
for len(queue) > 0 {
l := len(queue)
temp := []int{}
for i := 0; i < l; i++ {
node := queue[0]
queue = queue[1:]
temp = append(temp,node.Val)
for j := 0; j < len(node.Children); j++ {
queue = append(queue,node.Children[j])
}
}
ans = append(ans,temp)
}
return ans
}
递归解法
func traverse(root *Node,ans *[][]int,level int) {
if root == nil {
return
}
if len(*ans) - 1 < level {
*ans = append(*ans,[]int{})
}
(*ans)[level] = append((*ans)[level],root.Val)
for i := 0; i < len(root.Children); i++ {
traverse(root.Children[i],ans,level + 1)
}
}
func levelOrder1(root *Node) [][]int {
ans := [][]int{}
traverse(root,&ans,0)
return ans
}
总结：
勤思考。
结语
不管怎么样好好加油。
