(node: TreeNode, p: TreeNode, q: TreeNode)
| 15 | return lca |
| 16 | |
| 17 | def dfs(node: TreeNode, p: TreeNode, q: TreeNode) -> bool: |
| 18 | global lca |
| 19 | # Base case: a null node is neither 'p' nor 'q'. |
| 20 | if not node: |
| 21 | return False |
| 22 | node_is_p_or_q = node == p or node == q |
| 23 | # Recursively determine if the left and right subtrees contain 'p' |
| 24 | # or 'q'. |
| 25 | left_contains_p_or_q = dfs(node.left, p, q) |
| 26 | right_contains_p_or_q = dfs(node.right, p, q) |
| 27 | # If two of the above three variables are true, the current node is |
| 28 | # the LCA. |
| 29 | if (node_is_p_or_q + left_contains_p_or_q + right_contains_p_or_q == 2): |
| 30 | lca = node |
| 31 | # Return true if the current subtree contains 'p' or 'q'. |
| 32 | return (node_is_p_or_q or left_contains_p_or_q or right_contains_p_or_q) |
no outgoing calls
no test coverage detected