1123. Lowest Common Ancestor of Deepest Leaves

Link

Solution

DFS思路

• 推演的過程中要告訴我們什麼?

  • 狀態的更新 (global variable)

    • lca

    • deepest

  • 子問題的答案 (return value)

    • node 的子孫裡最底層的leaf 深度

helper function to return the max depth of tree whose root is node.

Keep tracking the deepest depth of the tree during traversal.

結算: 若是左右子樹的最大深度相同，就是lca

    TreeNode lca;
    int deepest = 0;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return lca;
    }
    
    public int dfs(TreeNode node, int depth){
        
        if(node == null){
            return depth - 1;
        }
        
        //中間產物
        deepest = Math.max(deepest, depth);        
        
        //推演
        int leftLeafMaxDepth = dfs(node.left, depth+1);
        int rightLeafMaxDepth = dfs(node.right, depth+1);
        
        //結算
        if(leftLeafMaxDepth == deepest && leftLeafMaxDepth == rightLeafMaxDepth){
            lca = node;
        }
        return Math.max(leftLeafMaxDepth, rightLeafMaxDepth);
    }