# 865. Smallest Subtree with all the Deepest Nodes

Given a binary tree rooted at `root`, the depth of each node is the shortest distance to the root.

A node is  deepest  if it has the largest depth possible among any node in the entire tree.

The subtree of a node is that node, plus the set of all descendants of that node.

Return the node with the largest depth such that it contains all the deepest nodes in its subtree.

Example 1:

``````Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:
``````

``````We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.
``````

Note:

• The number of nodes in the tree will be between 1 and 500.

• The values of each node are unique.

这道题给了我们一棵二叉树，让我们找包含所有最深结点的最小子树，就是返回这棵最小子树的根结点。题目中给了一个例子，因为有图，所以可以很直接的看出来最深的结点是7和4，那么包含这两个结点的最小子树的根结点是2，返回即可。其实最深的结点不一定只有两个，可能有很多个，比如对于一棵完全二叉树，即把例子图中的结点7和4去掉后，此时最深的结点就有四个，分别是6，2，0，8，都包含这些结点的子树就是原树本身了，要返回根结点。

``````class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
int diff = depth(root->left) - depth(root->right);
return (diff == 0) ? root : subtreeWithAllDeepest(diff > 0 ? root->left : root->right);
}
int depth(TreeNode* node) {
return !node ? 0 : max(depth(node->left), depth(node->right)) + 1;
}
};
``````

``````class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return helper(root).second;
}
pair<int, TreeNode*> helper(TreeNode* node) {
if (!node) return {0, NULL};
auto left = helper(node->left), right = helper(node->right);
int d1 = left.first, d2 = right.first;
return {max(d1, d2) + 1, (d1 == d2) ? node : (d1 > d2 ? left.second : right.second)};
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/865

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/discuss/146808/One-pass

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/discuss/146786/Simple-recursive-Java-Solution

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/discuss/146842/Short-and-concise-C%2B%2B-solution-using-DFS-3~5-lines

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation