This could be done recursivly. For each sub-tree, if the depth of its left sub-tree is the same as the depth of its right sub-tree, then return the node, else, return the deepper sub-tree's root.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
return self._helper(root)[0]
def _helper(self, node):
if node is None:
return None, 0
l = self._helper(node.left)
r = self._helper(node.right)
if l[1] == r[1]:
return node, l[1] + 1
elif l[1] < r[1]:
return r[0], r[1] + 1
else:
return l[0], l[1] + 1