865.Smallest Subtree with all the Deepest Nodes
求具有所有最深结点的最小子树
给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。 如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。 一个结点的子树是该结点加上 它的所有后代的集合。 返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
方法：当左右子树深度相同时，则根子树就是最小子树。当左子树深度大于右子树时，将左子树看做根节点，继续比较左子树的左右子树。同理，右子树也是一样的方法，最后得到所求的最小子树。
通过创建一个函数求子树深度。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
int DL= depth(root->left);
int DR = depth(root->right);
if (DL == DR)
return root;
else
return DL>DR? subtreeWithAllDeepest(root->left):subtreeWithAllDeepest(root->right);
}
private:
int depth(TreeNode* root)
{
if(root==NULL)
return 0;
int dl = depth(root->left);
int dr = depth(root->right);
return dl>dr ? dl+1:dr+1;
}
};
Last modified 1yr ago