/**

/**
 * Created by 1000132937 on 3/25/2018.
 */
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
public class NaryTreePathCost {
    static class TreeNode{
        int val;
        TreeNode[] children;
        public TreeNode(int val, int n) {
            this.val = val;
            this.children = new TreeNode[n];
        }
    }
    private static int minCost = Integer.MAX_VALUE;
    public List<Integer> findMinCostFromRoot2Leaf(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null ) {
            return result;
        }

        List<Integer> cur = new ArrayList<Integer>();
        cur.add(root.val);
        dfs(root, root.val, cur, result);
        return result;

    }

    private void dfs(TreeNode root, int cost, List<Integer> cur, List<Integer> result) {
        if (root.children == null || root.children.length == 0) {
            if (cost < minCost) {
                minCost = cost;
                result.clear();
                result.addAll(cur);
            }
            return;
        }

        for (TreeNode child : root.children) {
            cur.add(child.val);
            dfs(child, cost + child.val, cur, result);
            cur.remove(cur.size() - 1);
        }
    }
}