329*

Problem Statement

link: LeetCode.cn LeetCode Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4]

Input: root = [1] Output: [1]

Input: root = [0,1,3,null,2] Output: [2]

Solution Approach

Algorithm

Implement

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            if not root:
                return (None, 0)
            l = dfs(root.left)
            r = dfs(root.right)
            depth = max(l[1], r[1]) + 1
            if l[1] < r[1]:
                return (r[0], depth)
            elif l[1] > r[1]:
                return (l[0], depth)
            return (root, depth)
        return dfs(root)[0]
                

    
    

Twitter  facebook  Email