590. N 叉树的后序遍历

N 叉树的后序遍历

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

解法一: 深度优先遍历

go

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

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

解法二: 广度优先遍历

go

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

func postorder(root *Node) []int {
  ans := []int{}
  if root == nil {
    return ans
  }
  stack := []*Node{root}
  set := make(map[*Node]bool)
  for len(stack) > 0 {
    node := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    n := len(node.Children)
    if n > 0 && !set[node] {
      stack = append(stack, node)
      set[node] = true
      for i := n - 1; i >= 0; i-- {
        stack = append(stack, node.Children[i])
      }
    } else {
      ans = append(ans, node.Val)
    }
  }
  return ans
}