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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct Result {
11 struct TreeNode *node;
12 int depth;
13};
14
15struct Result dfs(struct TreeNode *node) {
16 if (!node) return (struct Result){NULL, 0};
17 struct Result left = dfs(node->left);
18 struct Result right = dfs(node->right);
19 if (left.depth > right.depth) return (struct Result){left.node, left.depth + 1};
20 if (right.depth > left.depth) return (struct Result){right.node, right.depth + 1};
21 return (struct Result){node, left.depth + 1};
22}
23
24struct TreeNode* subtreeWithAllDeepest(struct TreeNode* root) {
25 return dfs(root).node;
26}The C solution introduces a struct `Result` to manage both tree nodes and their respective depths. This structure simplifies the tracking of each node's depth during DFS traversal, ensuring the identification of the lowest common ancestor efficiently.
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.
The Python solution defines a helper function `height` to recursively compute the height from each node and a function `lcaDeepestLeaves` to find the node acting as the common ancestor of the deepest leaves. Comparisons between left and right heights guide the decision toward the correct subtree.