Lowest Common Ancestor of Deepest Leaves in an N-ary Tree
Problem statement
You are given a nonempty list records describing a tree in which a node may have any number of children. Read the records and return the ID of the lowest common ancestor of all deepest leaves. The root has depth zero. A node is its own ancestor, so one deepest leaf is its own answer.
Records use id:child1,child2,..., with id: for a leaf. IDs are nonnegative decimal integers written without spaces or leading zeroes, except for 0 itself. The first record identifies the root; all remaining records may be unordered. Child lists define ordered children, though their order does not change the ancestor answer.
Every ID has one record, every referenced child exists, and the records form one valid connected tree. The lowest common ancestor is the deepest node whose subtree contains all of the deepest leaves.
Function
lcaDeepestLeaves(records: String[]) → intExamples
Example 1
records = ["10:20,30","30:60","50:","20:40,50","40:","60:"]return = 10The deepest leaves 40, 50 and 60 span both root subtrees.
Example 2
records = ["1:2,3","3:","2:4,5","5:","4:"]return = 2The deepest leaves are 4 and 5, whose lowest common ancestor is 2.
Example 3
records = ["9:7","7:4","4:"]return = 4Leaf 4 is the only deepest leaf and is its own ancestor.
Constraints
1 <= records.length <= 2000.- IDs are in
0..1000000000; total record length is at most50000characters. - The records follow the stated grammar and form a valid tree.