1123. Lowest Common Ancestor of Deepest Leaves

 一刷

Version #1 One pass recursion

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 76.02% of Java online submissions for Lowest Common Ancestor of Deepest Leaves.

Memory Usage: 45.2 MB, less than 16.63% of Java online submissions for Lowest Common Ancestor of Deepest Leaves.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    class Pair {

        int maxDepth;

        TreeNode lca;

        public Pair(int maxDepth, TreeNode lca) {

            this.maxDepth = maxDepth;

            this.lca = lca;

        }

    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {

        Pair result = helper(root, 0);

        return result.lca;

    }

    

    private Pair helper(TreeNode node, int depth) {

        if (node == null) {

            return new Pair(-1, null);

        }

        depth++;

        if (node.left == null && node.right == null) {

            return new Pair(depth, node);

        }

        Pair left = helper(node.left, depth);

        Pair right = helper(node.right, depth);

        if (left.maxDepth > right.maxDepth) {

            return left;

        }

        if (left.maxDepth < right.maxDepth) {

            return right;

        }

        return new Pair(left.maxDepth, node);

    }

}