leetcode/236_lowest_common_ancestor_of_a_binary_tree.py at master · sn1572/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# -*- coding: utf-8 -*-
"""
Created on Tue Jul 28 16:02:04 2020

@author: mbolding3
"""


# Definition for a binary tree node.
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None


class Solution:


    def __init__( self ):
        self.root = None


    def reverse( self, node, last=None ):
        if node is None:
            return()
        self.reverse( node.left, node )
        self.reverse( node.right, node )
        node.right = last


    def get_ancestry( self, node ):
        # Assumes a reversed tree
        ancestry = []
        while node is not None:
            ancestry.append( node )
            node = node.right
        return( ancestry )


    def get_lca( self, p, q ):
        a_p = self.get_ancestry( p )
        a_q = self.get_ancestry( q )
        offset = -1
        limit = -min( len(a_p), len(a_q) )
        while ( offset-1 >= limit ) and ( a_p[ offset-1 ] == a_q[ offset-1 ] ):
            offset -= 1
        return( a_p[ offset ] )


    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if self.root != root:
            self.reverse( root )
            self.root = root
        return( self.get_lca( p, q ) )


if __name__ == '__main__':
    a = TreeNode(1)
    b = TreeNode(2)
    c = TreeNode(3)
    d = TreeNode(4)
    a.left = b
    a.right = c
    b.right = d
    sol = Solution()
    lca = sol.lowestCommonAncestor( a, d, c )
    print( lca.val )