Problem · Array
Flat Comments to a Nested Tree
Learn this problem● Medium
ByteDanceFULLTIMEPHONE SCREEN
ByteDanceFULLTIMEPHONE SCREENProblem statement
Convert a flat list of comments into a nested JSON forest. Comment i has the string fields ids[i], parentIds[i], and texts[i]. An empty parent ID marks a root; otherwise, the comment is a child of the comment whose ID equals its parent ID.
Preserve input order among roots and among siblings. Return a compact JSON array. Every object must contain the fields id, parent_id, text, and children, in that order. The children value is an array that follows the same rule. Escape strings according to JSON.
Function
buildCommentTree(ids: String[], parentIds: String[], texts: String[]) → StringExamples
Example 1
ids = ["1","2","3","4","5"]parentIds = ["","","1","2","3"]texts = ["A","B","C","D","E"]return = "[{\"id\":\"1\",\"parent_id\":\"\",\"text\":\"A\",\"children\":[{\"id\":\"3\",\"parent_id\":\"1\",\"text\":\"C\",\"children\":[{\"id\":\"5\",\"parent_id\":\"3\",\"text\":\"E\",\"children\":[]}]}]},{\"id\":\"2\",\"parent_id\":\"\",\"text\":\"B\",\"children\":[{\"id\":\"4\",\"parent_id\":\"2\",\"text\":\"D\",\"children\":[]}]}]"Comments 1 and 2 are roots. Comment 3 is under 1, comment 5 is under 3, and comment 4 is under 2.
Example 2
ids = ["c","r","s"]parentIds = ["r","","r"]texts = ["first","root","second"]return = "[{\"id\":\"r\",\"parent_id\":\"\",\"text\":\"root\",\"children\":[{\"id\":\"c\",\"parent_id\":\"r\",\"text\":\"first\",\"children\":[]},{\"id\":\"s\",\"parent_id\":\"r\",\"text\":\"second\",\"children\":[]}]}]"A child may appear before its parent in the flat input. The two children of r retain their relative input order.
Constraints
0 <= ids.length <= 100000.- The three arrays have equal length.
- IDs are unique nonempty printable ASCII strings of length at most
50. - Each parent ID is empty or names exactly one other comment.
- The parent relationships form a forest.
- Text has at most
200printable ASCII characters.