Powered By GitBook
865.Smallest Subtree with all the Deepest Nodes

求具有所有最深结点的最小子树

给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。 如果一个结点在整个树的任意结点之间具有最大的深度,则该结点是最深的。 一个结点的子树是该结点加上它的所有后代的集合。 返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
方法:当左右子树深度相同时,则根子树就是最小子树。当左子树深度大于右子树时,将左子树看做根节点,继续比较左子树的左右子树。同理,右子树也是一样的方法,最后得到所求的最小子树。
通过创建一个函数求子树深度。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
13
int DL= depth(root->left);
14
int DR = depth(root->right);
15
if (DL == DR)
16
return root;
17
else
18
return DL>DR? subtreeWithAllDeepest(root->left):subtreeWithAllDeepest(root->right);
19
20
}
21
private:
22
int depth(TreeNode* root)
23
{
24
if(root==NULL)
25
return 0;
26
int dl = depth(root->left);
27
int dr = depth(root->right);
28
return dl>dr ? dl+1:dr+1;
29
}
30
};
Copied!
Last modified 2yr ago
Copy link