Note: The question is exactly same as LC 865. Smallest Subtree with all the Deepest Nodes
Approach 1
Suppose a node’s left subtree’s (including node itself) max height amongst all leaves is left and that of right subtree (including node itself) is right. Now, for each node in DFS, if left == right >= max height encountered then this node should be the answer. Otherwise, if left == right < max height, this node cannot be the answer as it doesn’t contain any leaf with maximum depth (or height). If left != right, then this node does not contain the deepest leaf node OR there must be node below this node where left == right >= max height encountered so that node would be the answer. Consider this example:
3
/ \
5 1
/ | | \
6 2 0 8
/ \ \
7 4 9
Performing DFS:
- For node 6, left = 2 (it's own height), right = 2 (it's own height). Since maxHeight = 0 initially, left == right > maxHeight so 6 is our answer right now.
- For node 7, left = 3 (it's own height), right = 3 (it's own height). Since maxHeight = 2, left == right > maxHeight so 7 becomes answer.
- Similarly, 4 becomes answer then.
- For node 2, left = 3 (height of leaf 7), right = 3 (height of leaf 4). Since maxHeight = 3, left == right == maxHeight so 2 becomes the answer. This is because 2 contains both the deepest leaves 7 and 4.
- For node 5, left = 2 (height of leaf 6), right = 3 (height of leaf 7 or 4). Since left != right, 5 will not be the answer. Note that this is because we have to find the deepest node having all deepest leaves so 2 should be the answer not 5.
- For node 9, left = 3 (it's own height), right = 3 (it's own height). Since maxHeight = 3, left == right == maxHeight so 9 becomes the answer.
- For 0, left = 2 (it's own height), right = 3 (9's height). left != right.
- For 8, left = 2 (it's own height), right = 2 (it's own height). left == right < maxHeight.
- For 1, left = 3 (9's height), right = 2 (8's height). left != right.
- For 3, left = 3 (7 or 4's height), right = 3 (9's height). left == right == maxHeight so 3 becomes our answer!
Code:
class Solution {
public:
TreeNode* res = NULL;
int maxHeight = 0;
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
if (!root)
return NULL;
dfs(root, 0);
return res;
}
int dfs (TreeNode *node, int currHeight) {
if (node == NULL)
return currHeight-1;
int left = dfs(node->left, currHeight+1);
int right = dfs(node->right, currHeight+1);
if (left == right && left>=maxHeight) {
res = node;
maxHeight=left;
}
return max(left, right);
}
};
Time complexity: O(n)
Approach 2: Same idea, different implementation
Solution given by $lee215:
Explanation
Write a sub function deep(TreeNode root).
Return a pair(int depth, TreeNode subtreeWithAllDeepest)
In sub function deep(TreeNode root):
if root == null, return pair(0, null) left = deep(root.left) right = deep(root.left)
if left depth == right depth, deepest nodes both in the left and right subtree, return pair (left.depth + 1, root)
if left depth > right depth, deepest nodes only in the left subtree, return pair (left.depth + 1, left subtree)
if left depth < right depth, deepest nodes only in the right subtree, return pair (right.depth + 1, right subtree)
Complexity
Time O(N)
Space O(height)
Code:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return deep(root).second;
}
pair<int, TreeNode*> deep(TreeNode* root) {
if (!root) return {0, NULL};
pair<int, TreeNode*> l = deep(root->left), r = deep(root->right);
int d1 = l.first, d2 = r.first;
return {max(d1, d2) + 1, d1 == d2 ? root : d1 > d2 ? l.second : r.second};
}