## Friday, February 19, 2016

### Indeed: N-ary tree root to leaf min cost

Buttercola: Indeed: N-ary tree root to leaf min cost
N-ary tree, Each edge has a weight. Calculate the minimum path sum, and return the path nodes.

`    ``private` `static` `int` `minCost = Integer.MAX_VALUE;`
`    ``public` `List<Integer> findMinCostFromRootToLeaf(TreeNode root) {`
`        ``List<Integer> result = ``new` `ArrayList<>();`
`        ``if` `(root == ``null``) {`
`            ``return` `result;`
`        ``}`
`        `
`        ``List<Integer> curr = ``new` `ArrayList<>();`
`        ``curr.add(root.val);`
`        ``findMinCostHelper(root, root.val, curr, result);`
`        `
`        ``return` `result;`
`    ``}`
`    ``private` `void` `findMinCostHelper(TreeNode root, ``int` `cost, List<Integer> `
`                                   ``curr, List<Integer> result) {`

`        ``if` `(root.children == ``null` `|| root.children.length == ``0``) {`
`            ``if` `(cost < minCost) {`
`                ``minCost = cost;`
`                ``result.clear();`
`                ``result.addAll(curr);`
`            ``}`
`            ``return``;`
`        ``}`
`        `
`        ``for` `(TreeNode child : root.children) {`
`            ``curr.add(child.val);`
`            ``findMinCostHelper(child, cost + child.val, curr, result);`
`            ``curr.remove(curr.size() - ``1``);`
`        ``}`
`    ``}``    `
`    ``static` `class` `TreeNode {`
`        ``int` `val;`
`        ``TreeNode[] children;`
`        `
`        ``public` `TreeNode(``int` `val, ``int` `n) {`
`            ``this``.val = val;`
`            ``this``.children = ``new` `TreeNode[n];`
`        ``}`
`    ``}`