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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var subtreeWithAllDeepest = function(root) {
8 const dfs = (node) => {
9 if (!node) return {node: null, depth: 0};
10 const left = dfs(node.left);
11 const right = dfs(node.right);
12 if (left.depth > right.depth) return {node: left.node, depth: left.depth + 1};
13 if (right.depth > left.depth) return {node: right.node, depth: right.depth + 1};
14 return {node: node, depth: left.depth + 1};
15 };
16 return dfs(root).node;
17};The JavaScript code makes use of an inner "dfs" function that returns an object encapsulating the current subtree's root and the maximum depth achieved. By maintaining a consistent return structure, the approach ensures legibility and efficiency during DFS traversal, ultimately simplifying ancestor determination.
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.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int height(TreeNode* node) {
if (!node) return 0;
return std::max(height(node->left), height(node->right)) + 1;
}
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 provides a clean implementation relying on a self-defined `height` method, which evaluates the height of tree nodes in a recursive fashion. This bottom-up approach identifies the node serving as the common ancestor for all the deepest paths.