#705 Match a Descendant Selector

Implement a small querySelectorAll. Elements have tag, id, optional classes (a list of class names), and optional children.

A selector is one or more compound selectors separated by spaces, like ul.list li.item .label. A compound selector is an optional tag name or *, followed by any number of #id and .class parts, such as li, .item.active, #cart, or button#pay.btn. An element matches a compound selector when its tag matches (if one is given and it isn't *), its id matches (if given), and it has every listed class.

A space means "somewhere inside": an element matches the whole selector when it matches the last compound, and it has an ancestor matching the compound before that, which has an ancestor matching the one before that, and so on.

Write querySelectorAll(root, selector) that returns the ids of all matching elements in document order. root itself may match.

Input: root = {"tag":"div","id":"app","classes":["app"],"children":[{"tag":"ul","id":"cart","classes":["list"],"children":[{"tag":"li","id":"row1","classes":["item"],"children":[{"tag":"span","id":"name1","classes":["label"]},{"tag":"button","id":"del1","classes":["btn","danger"],"children":[{"tag":"svg","id":"icon1","classes":["icon"]}]}]},{"tag":"li","id":"row2","classes":["item","active"],"children":[{"tag":…, selector = "li.item .label"
Output: ["name1","name2"]

Input: root = {"tag":"div","id":"app","classes":["app"],"children":[{"tag":"ul","id":"cart","classes":["list"],"children":[{"tag":"li","id":"row1","classes":["item"],"children":[{"tag":"span","id":"name1","classes":["label"]},{"tag":"button","id":"del1","classes":["btn","danger"],"children":[{"tag":"svg","id":"icon1","classes":["icon"]}]}]},{"tag":"li","id":"row2","classes":["item","active"],"children":[{"tag":…, selector = ".active button"
Output: ["del2"]

Constraints

• The tree has 1 to 10^3 elements and is at most 100 levels deep.
• The selector has 1 to 10 compound selectors separated by one or more spaces. Names use letters, digits, -, and _.