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;
    }
};