Smallest Subtree with all the Deepest Nodes

Problem Id: 865 Difficulty: Medium Tag: Tree


Intuition

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.

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 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