0589. N Ary Tree Preorder Traversal

589. N-ary Tree Preorder Traversal#

题目 #

Given the `root` of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:

``````Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
``````

Example 2:

``````Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `0 <= Node.val <= 10^4`
• The height of the n-ary tree is less than or equal to `1000`.

Follow up: Recursive solution is trivial, could you do it iteratively?

解题思路 #

• N 叉树和二叉树的前序遍历原理完全一样。二叉树非递归解法需要用到栈辅助，N 叉树同样如此。将父节点的所有孩子节点逆序入栈，逆序的目的是为了让前序节点永远在栈顶。依次循环直到栈里所有元素都出栈。输出的结果即为 N 叉树的前序遍历。时间复杂度 O(n)，空间复杂度 O(n)。
• 递归解法非常简单，见解法二。

代码 #

``````package leetcode

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

// 解法一 非递归
func preorder(root *Node) []int {
res := []int{}
if root == nil {
return res
}
stack := []*Node{root}
for len(stack) > 0 {
r := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, r.Val)
tmp := []*Node{}
for _, v := range r.Children {
tmp = append([]*Node{v}, tmp...) // 逆序存点
}
stack = append(stack, tmp...)
}
return res
}

// 解法二 递归
func preorder1(root *Node) []int {
res := []int{}
preorderdfs(root, &res)
return res
}

func preorderdfs(root *Node, res *[]int) {
if root != nil {
*res = append(*res, root.Val)
for i := 0; i < len(root.Children); i++ {
preorderdfs(root.Children[i], res)
}
}
}
``````

Apr 8, 2023