问题描述
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, 10^4].
- 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?
问题分析
首先，常规解法是最简单的递归方式，参照二叉树的递归遍历即可，代码如下
示例代码-递归版
type Node struct {
Val int
Children []*Node
}
var ans []int
func preorder(root *Node) []int {
ans = []int{}
dfs(root)
return ans
}
func dfs(root *Node) {
if root == nil {
return
}
ans = append(ans, root.Val)
for _, v := range root.Children {
dfs(v)
}
}
示例代码-迭代版
题目的Follow Up要求我们不使用递归，而是用迭代法来解决；
这里我们需要借助stack，将root节点Push进stack之后，循环进行如下操作：
- 从stack中Pop，如果弹出节点为空，循环结束
- 如果不为空，将当前值添加到结果集中；同时逆序将当前节点的Children节点Push进stack中
借助stack我们即可实现N叉树的前序遍历，代码如下
type Node struct {
Val int
Children []*Node
}
func preorderV2(root *Node) []int {
stack := stack{}
stack.Push(root)
ans := []int{}
for {
node := stack.Pop()
if node == nil {
break
}
ans = append(ans, node.Val)
for i := len(node.Children) - 1; i >= 0; i-- {
stack.Push(node.Children[i])
}
}
return ans
}
type stack struct {
list []*Node
}
func (s *stack) Pop() *Node {
if len(s.list) == 0 {
return nil
}
ans := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return ans
}
func (s *stack) Push(node *Node) {
s.list = append(s.list, node)
}