In a Meta mobile UI hierarchy, each view is a node in a rooted tree. Given the root of the view tree and two target view IDs, return the ID of their lowest common ancestor (LCA), which is the deepest view that is an ancestor of both targets.
If either target view does not exist in the tree, return None.
Implement a function that takes:
root: a nested dictionary representing the root view, or Noneview_a: integer ID of the first target viewview_b: integer ID of the second target viewEach view node has the form:
{
"id": int,
"children": [view_node, ...]
}
Return:
None if one or both target views are missingExample 1
Input:
root = {"id": 1, "children": [{"id": 2, "children": [{"id": 4, "children": []}, {"id": 5, "children": []}]}, {"id": 3, "children": []}]}, view_a = 4, view_b = 5
Output:
2
Explanation: Views 4 and 5 share view 2 as their deepest common ancestor.
Example 2
Input:
root = {"id": 1, "children": [{"id": 2, "children": []}, {"id": 3, "children": []}]}, view_a = 2, view_b = 3
Output:
1
Explanation: The root view is the first common ancestor of both targets.
0 <= number of views <= 10^51 <= view id <= 10^9root = {"id": 1, "children": [{"id": 2, "children": [{"id": 4, "children": []}, {"id": 5, "children": []}]}, {"id": 3, "children": []}]}, view_a = 4, view_b = 5Output2WhyBoth views are under view `2`, and no deeper node is an ancestor of both.root = {"id": 1, "children": [{"id": 2, "children": []}, {"id": 3, "children": []}]}, view_a = 2, view_b = 3Output1WhyThe two target views are in different branches, so their first shared ancestor is the root.root = {"id": 7, "children": [{"id": 8, "children": [{"id": 9, "children": []}]}]}, view_a = 8, view_b = 9Output8WhyA node is considered an ancestor of itself, so the LCA of `8` and its descendant `9` is `8`.0 <= number of views <= 10^51 <= view id <= 10^9All view IDs are uniqueEach node contains a `children` listReturn `None` if one or both target views are not presentdef lowest_common_ancestor_view(root, view_a, view_b):
