Lowest Common Ancestor of Deepest Leaves

This approach tackles the problem by breaking it into two distinct, more straightforward subproblems. First, it performs a full traversal of the tree to identify all the leaf nodes that reside at the maximum possible depth. After collecting these leaves, it initiates a second traversal to find their lowest common ancestor (LCA).

• Pass 1: Find Deepest Leaves
  1. Initialize maxDepth = -1 and an empty list deepestLeaves.
  2. Define a recursive helper function findDeepestLeaves(node, depth).
  3. In the helper, if the node is a leaf, compare its depth with maxDepth. If depth > maxDepth, clear the list and add the current leaf. If depth == maxDepth, just add the current leaf.
  4. Traverse the entire tree by calling findDeepestLeaves(root, 0).
• Pass 2: Find LCA of Deepest Leaves
  1. If the deepestLeaves list contains only one node, return that node as it's the LCA of itself.
  2. Create a Set of the deepestLeaves for efficient O(1) lookups.
  3. Define another recursive helper function findLCA(node, targets).
  4. In this function, if the current node is null or is one of the target leaves, return the node.
  5. Recursively call findLCA for the left and right children.
  6. If the calls for both left and right subtrees return a non-null node, it means deepest leaves were found on both sides, making the current node the LCA. Return the current node.
  7. Otherwise, if only one side returned a non-null node, propagate that result up the recursion chain.
  8. The initial call findLCA(root, targets) will return the final answer.

This method involves two main passes over the tree.

Pass 1: Identify the Deepest Leaves First, we need to determine the maximum depth of the tree and find all leaf nodes at that depth. This can be done with a single Depth-First Search (DFS) traversal.

• We maintain a global variable maxDepth and a list deepestLeaves.
• We traverse the tree with a function findDeepestLeaves(node, depth).
• When we encounter a leaf node (node.left == null && node.right == null), we check its depth.
  • If depth > maxDepth, we've found a new deepest level. We update maxDepth, clear our deepestLeaves list, and add the current leaf.
  • If depth == maxDepth, we've found another leaf at the current maximum depth, so we add it to the list.

Pass 2: Find the Lowest Common Ancestor (LCA) Once we have the set of deepest leaves, we find their LCA.

• If there's only one deepest leaf, it is its own LCA.
• Otherwise, we use a standard LCA-finding algorithm. A recursive function findLCA(node, targets) is suitable. We convert our list of leaves to a Set for efficient lookups.
• This function returns the node itself if it's one of the targets. It recursively checks its left and right subtrees. If it gets non-null results from both children, it means targets exist in both subtrees, making the current node the LCA. If only one child returns a result, that result is propagated up.

import java.util.*;

class Solution {
    private int maxDepth = -1;
    private List<TreeNode> deepestLeaves = new ArrayList<>();

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        // Pass 1: Find the deepest leaves
        findDeepestLeaves(root, 0);

        // If only one, it's the LCA
        if (deepestLeaves.size() == 1) {
            return deepestLeaves.get(0);
        }

        // Pass 2: Find the LCA of the collected leaves
        Set<TreeNode> targets = new HashSet<>(deepestLeaves);
        return findLCA(root, targets);
    }

    private void findDeepestLeaves(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) { // It's a leaf
            if (depth > maxDepth) {
                maxDepth = depth;
                deepestLeaves.clear();
                deepestLeaves.add(node);
            } else if (depth == maxDepth) {
                deepestLeaves.add(node);
            }
            return;
        }
        findDeepestLeaves(node.left, depth + 1);
        findDeepestLeaves(node.right, depth + 1);
    }

    private TreeNode findLCA(TreeNode node, Set<TreeNode> targets) {
        if (node == null || targets.contains(node)) {
            return node;
        }
        TreeNode left = findLCA(node.left, targets);
        TreeNode right = findLCA(node.right, targets);
        if (left != null && right != null) {
            return node;
        }
        return left != null ? left : right;
    }
}