# Title Description

Given a N Fork tree , Returns the The former sequence traversal .

for example , Given a  `3 Fork tree ` :

Return its preorder traversal : `[1,3,5,6,2,4]`.

source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

# Their thinking

recursively , Visit according to The root node —— subtree The way to traverse the tree , When visiting subtrees , A subtree can also be used as n Fork tree , Returns when the node is empty , In this way, you can recurse .

# Solution code

Complexity analysis

Time complexity ：O(n), among n yes n The number of nodes in the cross tree . Each node is traversed exactly once .

Spatial complexity ：O(n), For the stack overhead in recursion , On average O(logn), At worst, the tree is chained , by O(n).

``````/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> preorder(Node root) {
helper(root);
return res;
}
public void helper(Node root){
if(root == null)
return ;