1123. Lowest Common Ancestor of Deepest Leaves - Medium

前往題目

想法

• DFS

思路

1. DFS
2. 往最深處找，找到大於當前已知最深的深度就更新，node也要一併更新因為有可能沒有共同ancestor這時答案就是leaf node本身
3. 左右都找到最深，並且每次都要判斷是否當前是最深leaf的ancestor以更新答案

Code

class Solution {
    TreeNode res;
    int maxDepth;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        res = new TreeNode();
        maxDepth = -1;

        dfs(root, 0);
        return res;
    }

    private int dfs(TreeNode node, int depth) {
        if (node == null) return 0;

        // Leaf
        if (node.left == null && node.right == null) {
            if (depth > maxDepth) {
                res = node;
                maxDepth = depth;
            }
            return depth;
        }

        int leftDepth = dfs(node.left, depth + 1);
        int rightDepth = dfs(node.right, depth + 1);
        

        // Found the parent which has the deepest leaf
        if (leftDepth == rightDepth && leftDepth == maxDepth) {
            res = node;
        }

        return Math.max(leftDepth, rightDepth);
    }
}