1123. Lowest Common Ancestor of Deepest Leaves

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
• The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

• dfs solution
• Time : O(n)
• Space : O(1)

c++

class Solution {
    pair<TreeNode*, int> helper(TreeNode* node, int level) {
        if(!node) return{nullptr, -1};
        if(!node->left and !node->right) return {node, level};
        auto [ln, ld] = helper(node->left, level + 1);
        auto [rn, rd] = helper(node->right, level + 1);
        if(ld == rd) return {node, ld};
        if(ld > rd) return {ln, ld};
        return {rn, rd};
    }
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return helper(root, 0).first;
    }
};

• lca solution
• Time : O(n + logn * logn)
  • dfs for O(n)
  • lca query for each O(logn)
  • maximum deeptest node count is log(n) (full binary tree)
  • so O(n + logn * logn)
• Space : O(n)

c++

/**
 * 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 {
    vector<vector<int>> deep;
    int LCA[1001][22];
    int lvl[1001];
    unordered_map<int, TreeNode*> mp;
    int id = 1;
    void dfs(TreeNode* node, int level, int par) {
        if(!node) return;
        if(deep.size() == level) deep.emplace_back();
        
        int me = id++;
        lvl[me] = level;
        deep[level].push_back(me);
        mp[me] = node;
        LCA[me][0] = par;
        
        dfs(node->left, level + 1, me);
        dfs(node->right, level + 1, me);
    }
    void init() {
        for(int i = 0; i < 21; i++) {
            for(int j = 1; j < id; j++) {
                if(LCA[j][i] == -1) continue;
                LCA[j][i + 1] = LCA[LCA[j][i]][i];
            }
        }
    }
    int query(int u, int v) {
        if(lvl[u] < lvl[v]) swap(u, v);
        int diff = lvl[u] - lvl[v];
        for(int i = 0; diff; i++) {
            if(diff & 1)
                u = LCA[u][i];
            diff >>= 1;
        }
        if(u == v) return u;
        for(int i = 21; i >= 0; i--) {
            if(LCA[u][i] == LCA[v][i]) continue;
            u = LCA[u][i];
            v = LCA[v][i];
        }
        u = LCA[u][0];
        return u;
    }
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        memset(LCA, -1, sizeof LCA);
        memset(lvl, -1, sizeof lvl);
        dfs(root, 0, -1);
        init();
        vector<int>& deepest = deep.back();
        int res = deepest.back(); deepest.pop_back();
        while(!deepest.empty()) {
            int u = deepest.back(); deepest.pop_back();
            res = query(u, res);
        }
        
        return mp[res];
    }
};