Lowest Common Ancestor of Deepest Leaves

Intuition

When doing DFS, we could add an additional variable depth which is the deepest leave's depth of the current node. Once the depth of its left node and right node is equal, we should set this node to lowest common ancestor.

Solution


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

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        self.lca = None
        self.depth = 0
        self._dfs(root, 0)
        return self.lca

    def _dfs(self, node, depth):
        if node.left is None and node.right is None:
            if depth >= self.depth:
                self.lca = node
                self.depth = depth
            return depth
        elif node.left is None:
            return self._dfs(node.right, depth + 1)
        elif node.right is None:
            return self._dfs(node.left, depth + 1)
        else:
            l = self._dfs(node.left, depth + 1)
            r = self._dfs(node.right, depth + 1)
            if l == r:
                if l >= self.depth:
                    self.lca = node
                    self.depth = l
            return max(l, r)