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.
# 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)