package leetcode;

import java.util.Stack;

/**
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class Problem236 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> path1 = getPath(root, p);
        Stack<TreeNode> path2 = getPath(root, q);
        int minSize = Math.min(path1.size(), path2.size());
        TreeNode lca = null;
        for (int i = 0; i < minSize; i++) {
            TreeNode node1 = path1.pop();
            TreeNode node2 = path2.pop();
            if (node1.val != node2.val) {
                break;
            } else {
                lca = node1;
            }
        }
        return lca;
    }

    private Stack<TreeNode> getPath(TreeNode root, TreeNode n) {
        if (root == null) {
            return null;
        }
        if (root == n) {
            Stack<TreeNode> path = new Stack<>();
            path.add(root);
            return path;
        }
        Stack<TreeNode> result = getPath(root.left, n);
        if (result != null) {
            result.add(root);
            return result;
        }
        result = getPath(root.right, n);
        if (result != null) {
            result.add(root);
            return result;
        }
        return result;
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Stack;%0A%0A
 /**%0A
@@ -378,157 +378,73 @@
     
-Stack%3CTreeNode%3E path1 = getPath(root, p);%0A        Stack%3CTreeNode%3E path2 = getPath(root, q);%0A        int minSize = Math.min(path1.size(), path2.size()
+LCA lca = new LCA();%0A        lowestCommonAncestor(root, p, q, lca
 );%0A 
@@ -454,70 +454,60 @@
     
-T
 re
-eNode lca = null
+turn lca.node
 ;%0A    
+%7D%0A%0A
     
-for (int i = 0; i %3C minSize; i++)
+private static class LCA
  %7B%0A 
@@ -505,35 +505,39 @@
 s LCA %7B%0A        
-   
+private
  TreeNode node1 
@@ -538,152 +538,103 @@
 node
-1 = path1.pop()
 ;%0A    
+%7D%0A%0A
     
-    TreeNode node2 = path2.pop();%0A            if (node1.val != node2.val) %7B%0A                break;%0A            %7D else %7B
+private static boolean lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q,
 %0A   
@@ -650,21 +650,10 @@
     
-lca = node1;%0A
+  
     
@@ -660,26 +660,24 @@
         
-%7D%0A
         
 %7D%0A      
@@ -664,34 +664,32 @@
             
-%7D%0A
         
 return lca;%0A
@@ -680,88 +680,17 @@
     
-return lca;%0A    %7D%0A%0A    private Stack%3CTreeNode%3E getPath(TreeNode root, TreeNode n
+  LCA lca
 ) %7B%0A
@@ -736,20 +736,21 @@
  return 
-null
+false
 ;%0A      
@@ -765,102 +765,82 @@
     
-if (root == n) %7B%0A            Stack%3CTreeNode%3E path = new Stack%3C%3E();%0A            path.add(root);
+boolean mid = false;%0A        if (root.val == p.val %7C%7C root.val == q.val) %7B
 %0A   
@@ -852,19 +852,18 @@
     
-return path
+mid = true
 ;%0A  
@@ -882,40 +882,43 @@
     
-Stack%3CTreeNode%3E result = getPath
+boolean left = lowestCommonAncestor
 (roo
@@ -925,17 +925,25 @@
 t.left, 
-n
+p, q, lca
 );%0A     
@@ -949,138 +949,139 @@
     
-if (resul
+boolean righ
 t 
-!
 = 
-null) %7B%0A            result.add(root);%0A            return result;%0A        %7D%0A        result = getPath(root.right, n);%0A
+lowestCommonAncestor(root.right, p, q, lca);%0A        if ((mid && left) %7C%7C (mid && right) %7C%7C (left && right)) %7B%0A    
     
@@ -1092,16 +1092,18 @@
 if (
-result !
+lca.node =
 = nu
@@ -1124,24 +1124,27 @@
     
-result.add(
+    lca.node = 
 root
-)
 ;%0A  
@@ -1149,38 +1149,25 @@
             
-return result;
+%7D
 %0A        %7D%0A 
@@ -1184,13 +1184,25 @@
 urn 
-resul
+left %7C mid %7C righ
 t;%0A 

Update problem 236