Sponsored
Sponsored
This approach leverages DFS to determine the depth of each node while recursively finding the subtree containing all the deepest nodes. By tracking depth, we can identify the lowest common ancestor of the deepest nodes, which will be the root of the smallest subtree containing them all.
Time Complexity: O(N), since all nodes must be visited.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
9 def dfs(node):
10 if not node: return (None, 0)
11 lca_left, depth_left = dfs(node.left)
12 lca_right, depth_right = dfs(node.right)
13 if depth_left > depth_right:
14 return (lca_left, depth_left + 1)
15 elif depth_right > depth_left:
16 return (lca_right, depth_right + 1)
17 else:
18 return (node, depth_left + 1)
19 return dfs(root)[0]The Python solution defines a DFS function that recursively traverses the tree, returning the lowest common ancestor and the maximum depth found. At each node, the function compares the maximum depths of its left and right children. If both have equal depth, the current node is part of the smallest subtree containing all deepest nodes.
This solution calculates the height of the tree nodes starting from the leaves (bottom-up). By evaluating the heights of left and right subtrees, the method determines the lowest common ancestor (LCA) of the deepest nodes, thereby identifying the desired subtree.
Time Complexity: O(N^2) in the worst case due to repeated height calculations.
Space Complexity: O(H), corresponding to recursion use by `height` method.
1
The C implementation harnesses recursion to compute tree heights, determining the correct subtree by checking matching subtree depths. It efficiently settles operations via comparison, focusing on simplicity in the bottom-up logic.