Tree Expression From Pairs
MediumTrees · Optiver
Each pair (P,C) in pairs says node P is the parent of node C. If the pairs form a valid binary tree, return it as an expression: a node is (, its label, the expressions of its children in ascending label order, then ), so a leaf is (C).
Otherwise return the first code below that applies:
E1:pairsis not one or more(X,Y)pairs, withXandYuppercase letters, separated by exactly one spaceE2: the same pair appears more than onceE3: a node has more than two childrenE4: more than one node is never a childE5: the pairs contain a cycle, or a node has two parents
Example 1
- Input:
- pairs = "(A,B) (A,D) (B,C)"
- Output:
- "(A(B(C))(D))"
- Explanation
- A has children B and D, in that order; B has the single child C.
Example 2
- Input:
- pairs = "(A,B) (C,B) (D,E)"
- Output:
- "E4"
- Explanation
- A, C and D are never children, and that outranks B having two parents.
Example 3
- Input:
- pairs = "(A,B) (C,D) (D,C)"
- Output:
- "E5"
Constraints
- 1 ≤
pairs.length ≤ 1000 pairsmay contain any printable ASCII characters- Return either the expression or exactly one of
"E1"to"E5"