A museum's rooms form a binary tree with distinct integer labels; the root is the lobby. Every night a guard makes a round that enters every room exactly once, following these rules:
- He starts in the lobby.
- From his current room he may step into any not-yet-visited child room (left or right, his choice).
- Otherwise he walks back to the parent room. Once he has walked back out of a room he never enters it again, so he only leaves a room when every room below it has been visited.
His log lists the rooms in the order he first entered them. A log may be damaged. Return the
length of the longest prefix of log that could be the start of the log of some complete round.
(An undamaged complete log returns len(log); a log that does not start with the lobby returns 0.)
Examples
1
/ \
2 3
/ \
4 5
Input: root = build_tree([1, 2, 3, 4, 5]), log = [1, 3, 2, 5, 4]
Output: 5
Input: root = build_tree([1, 2, 3, 4, 5]), log = [1, 2, 4, 3, 5]
Output: 3
Explanation: to reach 3 after 4 he must walk back out of 2 while 5 is unvisited.
Constraints
1 <= number of nodes <= 10**5; the depth can be close to the number of nodes.0 <= len(log) <= 2 * 10**5; entries are integers, possibly repeated or not in the tree.- Target complexity: O(n + len(log)).
Goals
- Check a sequence against every depth-first order the tree allows, without listing them
- Simulate the walk with an explicit stack of rooms still open
- Find the exact position of the first entry that breaks the rules