1123. Lowest Common Ancestor of Deepest Leaves

https://www.cnblogs.com/grandyang/p/11397303.html

就先从最简单的情况开始分析吧，

• 假如 root 为空，则直接返回 nullptr，

• 假如 root 没有子结点，其本身就是最深叶结点，返回 root。

• 若 root 有左右子结点，说明左右子树存在，通常情况下我们会对左右子结点调用递归，那么返回的就是左右子树分别的最深叶结点的最小公共父节点，

但是问题来了，就算分别知道了左右子树的最深结点的 LCA，怎么推出当前树的 LCA？

• 若左子树的最深叶结点的深度更深，则应该返回左子树的 LCA，

• 若右子树的最深叶结点的深度更深，则应该返回右子树的 LCA，

• 若二者一样深，则要返回当前结点。

这样的话，对于每个结点 node，必须要分别知道其左右子树的最深叶结点的深度才行，可以使用一个 getDepth 函数来求任意结点到叶结点的最大深度，叶结点本身的深度为0。有了这个函数，就可以对当前结点的左右子结点计算深度，若深度相同，则返回当前结点，否则对深度大的子结点调用递归，怎么隐约感觉有些二分搜索法的影子在里面

T: O(n^2)

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root == null) {
            return null;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (left == right) {
            return root;
        }
        return (left > right) ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right);
    }
    private int getDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(getDepth(root.left), getDepth(root.right))+1;
    }
}

由于计算深度的函数 getDepth 存在大量的重复计算，可以使用一个 HashMap 来保存已经算过深度的结点，这样再次遇到的时候，直接从 HashMap 中取值即可，可以使计算效率更高一些

T: O(n)

class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if (root == null) {
            return null;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (left == right) {
            return root;
        }
        return (left > right) ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right);
    }
    private int getDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        map.put(root, Math.max(getDepth(root.left), getDepth(root.right))+1);
        return map.get(root);
    }
}