package leetcode;

/**
 * https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
 */
public class Problem1123 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        // TODO
        return null;
    }

    public static void main(String[] args) {
        Problem1123 prob = new Problem1123();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root = prob.lcaDeepestLeaves(root);
        System.out.println(root); // 1
        System.out.println(root.left); // 2
        System.out.println(root.right); // 3


        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root = prob.lcaDeepestLeaves(root);
        System.out.println(root); // 4

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root = prob.lcaDeepestLeaves(root);
        System.out.println(root); // 2
        System.out.println(root.left); // 4
        System.out.println(root.right); // 5
    }
}

@@ -352,175 +352,62 @@
     
-// TODO%0A        return null;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1123 prob = new Problem1123();%0A        TreeNode root = new TreeNode(1);
+if (root == null) %7B%0A            return null;%0A        %7D
 %0A   
@@ -415,827 +415,399 @@
     
-root.
+int 
 left = 
-new TreeNode(2);%0A        root.right = new TreeNode(3);%0A        root = prob.lcaDeepestLeaves(root);%0A        System.out.println(root); // 1%0A        System.out.println(root.left); // 2%0A        System.out.println(root.right); // 3%0A%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.right = new TreeNode(3);%0A        root.left.left = new TreeNode(4);%0A        root = prob.lcaDeepestLeaves(root);%0A        System.out.println(root); // 4%0A
+height(root.left);%0A        int right = height(root.right);%0A        if (left == right) %7B%0A            return root;%0A        %7D%0A        return left %3E right ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right);
 %0A    
+%7D%0A%0A
     
-root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.righ
+private static int height(TreeNode root) %7B%0A        if (roo
 t =
+=
  n
-ew TreeNode(3);%0A        root.left.left = new TreeNode(4);%0A        root.left.right = new TreeNode(5);%0A        root = prob.lcaDeepestLeaves(root);%0A        System.out.println(root); // 2%0A        System.out.println(root.left); // 4%0A        System.out.println
+ull) %7B%0A            return 0;%0A        %7D%0A        return 1 + Math.max(height(root.left), height
 (roo
@@ -818,14 +818,10 @@
 ght)
+)
 ;
- // 5
 %0A   

Solve problem 1123