589. N-ary Tree Preorder Traversal #

Problem #

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?

Problem Summary #

Given an N-ary tree, return the preorder traversal of its node values. An N-ary tree is serialized in the input using level-order traversal, with each group of child nodes separated by the null value null (see the examples).

Solution Approach #

• The principle of preorder traversal for an N-ary tree is exactly the same as for a binary tree. The non-recursive solution for a binary tree needs a stack as auxiliary storage, and the same applies to an N-ary tree. Push all child nodes of the parent node onto the stack in reverse order. The purpose of reversing is to ensure that the preorder node is always on top of the stack. Continue looping until all elements in the stack have been popped. The output result is the preorder traversal of the N-ary tree. The time complexity is O(n), and the space complexity is O(n).
• The recursive solution is very simple; see Solution 2.

Code #

package leetcode

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

// Solution 1: Iterative
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...) // store nodes in reverse order
		}
		stack = append(stack, tmp...)
	}
	return res
}

// Solution 2: Recursive
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)
		}
	}
}