589. N 叉树的前序遍历

N 叉树的前序遍历

• 难度: easy
• 原始链接: https://leetcode.cn/problems/n-ary-tree-preorder-traversal
• 标签: 前序遍历

解法一: 递归

go

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

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

解法二: 迭代

go

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

func preorder(root *Node) []int {
  ans := []int{}
  if root == nil {
    return ans
  }
  stack := []*Node{root}
  for len(stack) > 0 {
    node := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    ans = append(ans, node.Val)
    for i := len(node.Children) - 1; i >= 0; i-- {
      stack = append(stack, node.Children[i])
    }
  }
  return ans
}