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 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public TreeNode subtreeWithAllDeepest(TreeNode root) {
10 return dfs(root).node;
11 }
12 private Result dfs(TreeNode node) {
13 if (node == null) return new Result(null, 0);
14 Result left = dfs(node.left);
15 Result right = dfs(node.right);
16 if (left.depth > right.depth) return new Result(left.node, left.depth + 1);
17 if (right.depth > left.depth) return new Result(right.node, right.depth + 1);
18 return new Result(node, left.depth + 1);
19 }
20 private class Result {
21 TreeNode node;
22 int depth;
23 Result(TreeNode n, int d) {
24 node = n;
25 depth = d;
26 }
27 }
28}This Java solution uses a helper class "Result" to keep track of the node and its depth. The `dfs` function checks both left and right subtrees of a node recursively. When both subtrees have the same depth, it returns the current node as the lowest common ancestor.
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.
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int Height(TreeNode node) {
if (node == null) return 0;
return Math.Max(Height(node.left), Height(node.right)) + 1;
}
public TreeNode SubtreeWithAllDeepest(TreeNode root) {
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return SubtreeWithAllDeepest(root.left);
else return SubtreeWithAllDeepest(root.right);
}
}The C# solution delivers tree traversal using the recursive `Height` method, balancing ease of comprehension with functional capabilities. The method makes key comparisons between calculated left and right subtree depths to decide on the optimal subtree location.