具有所有最深节点的最小子树

/*
 * 思路：
 * 1. 使用深度优先搜索 (DFS) 计算每个节点的深度。
 * 2. 使用 Java Stream 找出所有最深节点。
 * 3. 找到这些最深节点的最近公共祖先 (LCA)。
 * 4. 返回这个公共祖先节点。
 */

import java.util.*;
import java.util.stream.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private Map<TreeNode, Integer> depthMap = new HashMap<>();
    private int maxDepth = 0;
    private TreeNode lca;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        calculateDepth(root, 0);
        List<TreeNode> deepestNodes = depthMap.entrySet().stream()
            .filter(entry -> entry.getValue() == maxDepth)
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());
        lca = findLCA(root, new HashSet<>(deepestNodes));
        return lca;
    }

    private void calculateDepth(TreeNode node, int depth) {
        if (node == null) return;
        depthMap.put(node, depth);
        maxDepth = Math.max(maxDepth, depth);
        calculateDepth(node.left, depth + 1);
        calculateDepth(node.right, depth + 1);
    }

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