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 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
Example 2:
Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.
Example 3:
Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
Constraints:
The number of nodes in the tree will be in the range [1, 500].
We design a function $\textit{dfs}(\textit{root})$ that returns the smallest subtree containing all the deepest nodes in the subtree rooted at $\textit{root}$, as well as the depth of the subtree rooted at $\textit{root}$.
The execution process of the function $\textit{dfs}(\textit{root})$ is as follows:
If $\textit{root}$ is null, return $\text{null}$ and $0$.
Otherwise, recursively calculate the smallest subtree and depth of the left and right subtrees of $\textit{root}$, denoted as $l$ and $l_d$, and $r$ and $r_d$, respectively. If $l_d > r_d$, then the smallest subtree containing all the deepest nodes in the subtree rooted at the left child of $\textit{root}$ is $l$, with a depth of $l_d + 1$. If $l_d < r_d$, then the smallest subtree containing all the deepest nodes in the subtree rooted at the right child of $\textit{root}$ is $r$, with a depth of $r_d + 1$. If $l_d = r_d$, then $\textit{root}$ is the smallest subtree containing all the deepest nodes, with a depth of $l_d + 1$.
Finally, return the first element of the result of $\textit{dfs}(\textit{root})$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsubtreeWithAllDeepest(self,root:Optional[TreeNode])->Optional[TreeNode]:defdfs(root:Optional[TreeNode])->Tuple[Optional[TreeNode],int]:ifrootisNone:returnNone,0l,ld=dfs(root.left)r,rd=dfs(root.right)ifld>rd:returnl,ld+1ifld<rd:returnr,rd+1returnroot,ld+1returndfs(root)[0]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsubtreeWithAllDeepest(root*TreeNode)*TreeNode{typepairstruct{node*TreeNodedepthint}vardfsfunc(*TreeNode)pairdfs=func(root*TreeNode)pair{ifroot==nil{returnpair{nil,0}}l,r:=dfs(root.Left),dfs(root.Right)ld,rd:=l.depth,r.depthifld>rd{returnpair{l.node,ld+1}}ifld<rd{returnpair{r.node,rd+1}}returnpair{root,ld+1}}returndfs(root).node}