aboutsummaryrefslogtreecommitdiff
path: root/low_common_ancestor_leaf.py
blob: 4b0036f65cb0ceb1a3707227d87c360ace994320 (plain)
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
# 1123. Lowest Common Ancestor of Deepest Leaves
import leetcode

"""
given the 'root' of a binary tree, return the lowest common ancestor of its
deepest leaves. recall that the node of a binary tree is a leaf if and only
if it has no children, the depth of the root of the tree is 0. if the depth
of a node is 'd', the depth of each of its children is 'd + 1'. and the
lowest common ancestor of a set 's' is the node 'a' with the largest depth
such that every node in 's' is in the subtree with root 'a'.
"""


class Solution(object):
    def lcaDeepestLeaves(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """

        def depth(node):
            if not node:
                return 0
            return max(depth(node.left), depth(node.right)) + 1

        def dfs(node, m, n):
            if not node:
                return None
            if m - 1 == n:
                return node
            l = dfs(node.left, m, n + 1)
            r = dfs(node.right, m, n + 1)
            if l and r:
                return node
            return l if l else r

        m = depth(root)
        return dfs(root, m, 0)


if __name__ == "__main__":
    obj = Solution()
    r1 = leetcode.treenode_build(root=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    r2 = leetcode.treenode_build(root=[1])
    r3 = leetcode.treenode_build(root=[0, 1, 3, None, 2])
    print(obj.lcaDeepestLeaves(r1))
    print(obj.lcaDeepestLeaves(r2))
    print(obj.lcaDeepestLeaves(r3))