Leetcode 1223 LCA of Deepest TreeNode

题意，找到所有最深的叶子节点的LCA
https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/

第一个想法是模块的想法, LCA +找到所有最深的叶子节点两两组合 可行，但是算法复杂度很高而且你先要从顶到下，再从下到顶再算一遍算法复杂度太高

第二个想法，利用后续位置进行计算，好处是，我在后续位置可以知道更多的信息，比如左右子树的深度信息此时是已知的。二叉树的分治算法本质上是一种后序遍历。
构造一个函数，这个函数能够返回一个lcaDeepestLeaves+以root为根的树的深度，如果左子树的深度 > 右子树的深度，我只需要返回左子树的答案，因为这意味着左边深度大，右边的叶子节点都被舍弃了，反之对右子树也成立
但是如果一样深，那我要返回root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return dfs(root).second;
    }
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (!node) {
            return {0, nullptr};
        }
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        if(left.first > right.first) {
            return {left.first + 1, left.second};
        } else
            if (left.first < right.first) {
                return {right.first + 1, right.second};
            }
        return {left.first + 1, node};
        }
    };