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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode SubtreeWithAllDeepest(TreeNode root) {
10 return DFS(root).node;
11 }
12 private (TreeNode node, int depth) DFS(TreeNode node) {
13 if (node == null) return (null, 0);
14 var left = DFS(node.left);
15 var right = DFS(node.right);
16 if (left.depth > right.depth) return (left.node, left.depth + 1);
17 if (right.depth > left.depth) return (right.node, right.depth + 1);
18 return (node, left.depth + 1);
19 }
20}The C# solution employs a tuple-like ValueTuple<TreeNode, int> to maintain data in a more structured and type-safe manner. This approach aids clarity and consistency, particularly when returning complex results such as node and depth pairs during the recursive DFS calls.
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.
This Java solution leverages a `height` utility method to evaluate depth from bottom to top. By recursively recalculating heights, it pinpoints the smallest subtree enclosing all deepest nodes. The approach emphasizes logical decision-making based on subtree heights.