Leetcode 1790 Solution

This article provides solution to leetcode question 1790 (lowest-common-ancestor-of-a-binary-tree-iii)
Categories:
Tags:
Access this page by simply typing in "lcs 1790" in your browser address bar if you have bunnylol configured.

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]