LeetCode 865. 具有所有最深结点的最小子树（递归）

示例：
输入：[3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的结点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的结点。
输入 "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" 是对给定的树的序列化表述。
输出 "[2, 7, 4]" 是对根结点的值为 2 的子树的序列化表述。
输入和输出都具有 TreeNode 类型。
 
提示：
树中结点的数量介于 1 和 500 之间。
每个结点的值都是独一无二的。

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        if(!root)
    		return NULL;
    	int hl = height(root->left);
    	int hr = height(root->right);
    	if(hl == hr)
    		return root;
    	else if(hl < hr)
    		return subtreeWithAllDeepest(root->right);
		else
    		return subtreeWithAllDeepest(root->left);
    }

    int height(TreeNode* root)
    {
    	if(!root)
    		return 0;
    	return 1+max(height(root->left),height(root->right));
    }
};

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }

    pair<int, TreeNode*> dfs(TreeNode* root)//返回深度，节点
    {
        if(!root)
            return {0, NULL};
        pair<int, TreeNode*> l = dfs(root->left);
        pair<int, TreeNode*> r = dfs(root->right);
        if(l.first == r.first)//左右高度一样，返回当前root，深度返回时都要+1
            return {l.first+1, root};
        else if(l.first > r.first)
            return {l.first+1, l.second};//左边高，返回左边找到的节点
        else
            return {r.first+1, r.second};
    }
};