1123. Lowest Common Ancestor of Deepest Leaves

Hint

/**
 * 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)
    {
        // If the tree is empty, return nullptr

        // Get the depth of the left and right subtrees

        // If the depths are equal, the current node is the LCA of the deepest leaves
        
        // If the left subtree is deeper, continue the search in the left subtree
        
        // Otherwise, continue the search in the right subtree
    }

    // This method calculates the depth of a given node
    int getDepth(TreeNode* node)
    {
        // If the node is null, return 0 as the depth
        // Recursively get the depth of the left and right subtrees and add 1 for the current node
    }
};

Solution

/**
 * 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)
    {
        if (!root) return nullptr;
        
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        
        if (left == right) return root;
        return (left > right) ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);        
    }

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

• 時間複雜度：
  $O(n^2)$
• 空間複雜度：
  $O(h)$

Hint - Optimization

/**
 * 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)
    {
        // Start the depth-first search from the root
    }

    // This method performs a depth-first search and returns a pair containing the LCA and the depth
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        // If the node is null, return {nullptr, 0} indicating a depth of 0

        // Recursively perform DFS on the left and right subtrees

        // If the left subtree is deeper, return the left LCA and increase the depth by 1
        // If the right subtree is deeper, return the right LCA and increase the depth by 1
        // If both subtrees have the same depth, the current node is the LCA
    }
};

Solution - Optimization

/**
 * 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).first;
    }
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        if (!node) return {nullptr, 0};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);

        if (left.second > right.second) return {left.first, left.second + 1};
        if (left.second < right.second) return {right.first, right.second + 1};
        return {node, left.second + 1};
    }    
};

• 時間複雜度：
  $O(n)$
• 空間複雜度：
  $O(h)$