Leetcode 1790 Solution

This article provides solution to leetcode question 1790 (lowest-common-ancestor-of-a-binary-tree-iii)

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii

Solution

""" # Definition for a Node. class Node: def __init__(self, val): self.val = val self.left = None self.right = None self.parent = None """
class Solution: def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node': node = p nodes1 = [p] while node: nodes1.append(node) node = node.parent
node = q nodes2 = [q] while node: nodes2.append(node) node = node.parent
i = len(nodes1) - 1 j = len(nodes2) - 1
while i >= 0 and j >= 0 and nodes1[i] == nodes2[j]: i -= 1 j -= 1
return nodes1[i + 1]