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 <utility>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* subtreeWithAllDeepest(TreeNode* root) {
13 return dfs(root).first;
14 }
15 std::pair<TreeNode*, int> dfs(TreeNode* node) {
16 if (!node) return {nullptr, 0};
17 auto left = dfs(node->left);
18 auto right = dfs(node->right);
19 if (left.second > right.second) return {left.first, left.second + 1};
20 if (right.second > left.second) return {right.first, right.second + 1};
21 return {node, left.second + 1};
22 }
23};In the C++ solution, the `dfs` function returns a pair consisting of the current subtree's lowest common ancestor and its maximum depth. This allows traversing the tree in a concise and functional manner, maintaining the depth information at each step to identify the smallest valid subtree.
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 JavaScript code implements an internal `height` function strategy to catalyze the assessment and comparison of tree heights across subtrees. This effectively points out the deepest nodes' common ancestor through a bottom-up evaluation technique.