429. N 叉树的层序遍历

N 叉树的层序遍历

• 难度: medium
• 原始链接: https://leetcode.cn/problems/n-ary-tree-level-order-traversal
• 标签: 深度优先遍历, 广度优先遍历

解法一: 深度优先遍历

go

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
  ans := [][]int{}
  var dfs func(node *Node, depth int)
  dfs = func(node *Node, depth int) {
    if node == nil {
      return
    }
    if len(ans) <= depth {
      ans = append(ans, []int{})
    }
    ans[depth] = append(ans[depth], node.Val)
    depth++
    for _, child := range node.Children {
      dfs(child, depth)
    }
  }
  dfs(root, 0)
  return ans
}

解法二: 广度优先遍历

go

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
  ans := [][]int{}
  if root == nil {
    return ans
  }
  queue := []*Node{root}
  for len(queue) > 0 {
    size := len(queue)
    nodes := make([]int, size)
    for i := 0; i < size; i++ {
      nodes[i] = queue[i].Val
      for _, child := range queue[i].Children {
        queue = append(queue, child)
      }
    }
    queue = queue[size:]
    ans = append(ans, nodes)
  }
  return ans
}