List Every Root-to-Leaf Path
Problem statement
Return every path from the root to a leaf in the tree described by parents. Each returned path is an array of node indices, starting with the root and ending with a leaf.
Nodes are numbered from 0 to parents.length - 1. Node 0 is the root and has parent -1. Every other parents[i] identifies the parent of node i. Each node may have any number of children; parent indices need not be smaller than child indices.
Return the paths in lexicographic order of their integer arrays: compare the first differing node index, or put a shorter prefix first. An empty tree returns an empty array. A single-node tree returns [[0]].
Function
rootLeafPaths(parents: int[]) → int[][]Examples
Example 1
parents = [-1,0,0,1,1]return = [[0,1,3],[0,1,4],[0,2]]The leaves are 3, 4, and 2. Their complete root paths are returned in lexicographic order: the two paths through node 1 come before the path through node 2.
Example 2
parents = [-1,4,0,2,2]return = [[0,2,3],[0,2,4,1]]Node 1 has parent 4, so parent indices do not determine traversal order. The leaves are 3 and 1, reached along the two returned paths.
Example 3
parents = [-1]return = [[0]]The root is itself a leaf, so its complete path is [0].
Constraints
0 <= parents.length <= 100-1 <= parents[i] <= 99- For nonempty input,
parents[0] == -1; every other parent is a valid node index. The parent links form one tree rooted at node0, with no cycle.