Given two nodes of a binary tree p and q, return theirlowest common ancestor (LCA).Each node will have a reference to its parent node. The definition for Node is below:
class Node { public int val; public Node left; public Node right; public Node parent;}
According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output: 5Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.
from __future__ import annotationsclass Node: def __init__(self, val: int = 0) -> None: self.val = val self.left: Node | None = None self.right: Node | None = None self.parent: Node | None = Noneclass Solution: # Time: O(h) where h is the height of the tree # Space: O(1) def lowest_common_ancestor(self, p: Node, q: Node) -> Node: a: Node | None = p b: Node | None = q while a is not b: a = q if a.parent is None else a.parent b = p if b.parent is None else b.parent assert a is not None return a
