アルゴリズム:Nフォークツリーの前順遍歴アルゴリズム共有

//1.  
	public List preorder(Node root) {
		List list = new ArrayList();
		if (root == null) return list;	
		
		list.add(root.val);
		pre_order(list, root.children);
		
		return list;
    }
	
	public void pre_order(List list, List subList) {
		if (subList == null || subList.size() == 0) return;
		
		for(Node n : subList) {
			if (n == null) return;
			list.add(n.val);
			pre_order(list, n.children);
		}
	}

//2.  
	 public List preorder(Node root) {
		 LinkedList input = new LinkedList<>();
		 LinkedList output = new LinkedList<>();
	        if (root == null) {
	            return output;
	        }

	        input.add(root);
	        while (!input.isEmpty()) {
	            Node node = input.pollLast();
	            output.add(node.val);
	            if (node.children != null) {
	            	Collections.reverse(node.children);
		            for (Node item : node.children) {
		            	input.add(item);
		            }
	            }
	        }
	        return output;
	    }