865. Smallest Subtree with all the Deepest Nodes

O(n) time O(h) space

/**
 * 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) {
        dfs(root, 1);
        return res;
    }

    int dfs(TreeNode *root, int depth) { // depth是从根到当前结点的深度，返回当前这棵树的深度
        if (!root) return 0;
        int l = dfs(root->left, depth + 1); // 子树的深度
        int r = dfs(root->right, depth + 1);
        if (l == r && depth + l >= mx) { // find the lowest root that covers all the deepest leaves
            mx = depth + l;
            res = root;
        }
        return max(l, r) + 1;
    }

    TreeNode *res = nullptr;
    int mx = 0;
};

/**
 * 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) {
        return dfs(root).first;
    }

    pair<TreeNode *, int> dfs(TreeNode *root) {
        if (!root) return {root, 0};
        auto l = dfs(root->left), r = dfs(root->right);
        if (l.second == r.second) return {root, l.second + 1};
        if (l.second > r.second) return {l.first, l.second + 1};
        return {r.first, r.second + 1};
    }
};