LeetCode 865: Smallest Subtree with all the Deepest Nodes
Problem Description
Explanation
To find the smallest subtree with all the deepest nodes, we need to first determine the depth of each node in the tree. Then, we can traverse the tree to find the deepest nodes. Finally, we can identify the smallest subtree that contains all the deepest nodes.
- Calculate the depth of each node in the tree.
- Traverse the tree to find the deepest nodes.
- Identify the smallest subtree that contains all the deepest nodes.
Time complexity: O(n) - where n is the number of nodes in the tree. Space complexity: O(n) - for the recursive stack space.
Solutions
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return dfs(root).node;
}
private Result dfs(TreeNode node) {
if (node == null) {
return new Result(null, 0);
}
Result left = dfs(node.left);
Result right = dfs(node.right);
if (left.depth > right.depth) {
return new Result(left.node, left.depth + 1);
} else if (left.depth < right.depth) {
return new Result(right.node, right.depth + 1);
} else {
return new Result(node, left.depth + 1);
}
}
private class Result {
TreeNode node;
int depth;
Result(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
}Related LeetCode Problems
Loading editor...