leetcode-practice-python/0235__lowest_common_ancestor_of_a_binary_search_tree.py at master · Philosoft/leetcode-practice-python · 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
69
70
71
72
73
74
75
76
77
78
from unittest import TestCase

from lib.TreeNode import TreeNode, build_tree


class Solution(TestCase):
    def test_example_1(self):
        root = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
        p = root.left
        q = root.right

        self.assertEqual(root, self.lowestCommonAncestor(root, p, q))
        self.assertEqual(root, self.lowestCommonAncestorFirstApproach(root, p, q))

    def test_example_2(self):
        root = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
        p = root.left
        q = root.left.right

        self.assertEqual(root.left, self.lowestCommonAncestor(root, p, q))
        self.assertEqual(root.left, self.lowestCommonAncestorFirstApproach(root, p, q))

    def test_example_3(self):
        root = build_tree([2, 1, None])
        p = root
        q = root.left

        self.assertEqual(root, self.lowestCommonAncestor(root, p, q))
        self.assertEqual(root, self.lowestCommonAncestorFirstApproach(root, p, q))

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        return root

    def lowestCommonAncestorFirstApproach(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        path = []

        def trace_path(start: TreeNode, target: int) -> None:
            path.append(start.val)

            if start.val == target:
                return

            if target > start.val:
                return trace_path(start.right, target)
            return trace_path(start.left, target)

        trace_path(root, p.val)
        path1 = path.copy()
        path = []
        trace_path(root, q.val)
        path2 = path

        if len(path1) >= len(path2):
            search_in = set(path1)
            search_from = path2
        else:
            search_in = set(path2)
            search_from = path1
        while search_from:
            t = search_from.pop()
            if t in search_in:
                intersection = t
                break
        h = root
        while True:
            if h.val == intersection:
                return h

            if intersection > h.val:
                h = h.right
            else:
                h = h.left