1123. Lowest Common Ancestor of Deepest Leaves

postorder 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* lcaDeepestLeaves(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;
};

对于当前的这棵树，分别获取左子树和右子树的最深叶节点的lca以及最大深度，如果左右两边最大深度相等，则root是当前这棵树的最深叶节点的lca，返回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* lcaDeepestLeaves(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};
    }
};

bfs O(n) time O(n) 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* lcaDeepestLeaves(TreeNode* root) {
        if (!root) return root;
        unordered_map<TreeNode *, TreeNode *> parent;
        unordered_set<TreeNode *> s;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            s.clear();
            for (int i = q.size(); i > 0; --i) {
                auto n = q.front(); q.pop();
                s.insert(n);
                if (n->left) {
                    q.push(n->left);
                    parent[n->left] = n;
                }
                if (n->right) {
                    q.push(n->right);
                    parent[n->right] = n;
                }
            }
        }
        while (s.size() > 1) {
            unordered_set<TreeNode *> t;
            t.swap(s);
            for (auto n : t) {
                s.insert(parent[n]);
            }
        }
        return *begin(s);
    }
};