package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * 236. Lowest Common Ancestor of a Binary Tree
 *
 * Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
 * According to the definition of LCA on Wikipedia:
 * “The lowest common ancestor is defined between two nodes v and w as the lowest node in T
 * that has both v and w as descendants (where we allow a node to be a descendant of itself).”

           _______3______
          /              \
      ___5__          ___1__
    /      \        /      \
   6      _2       0       8
  / \
 7   4

 For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.
 Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.*/

public class _236 {

    /**We need to find TWO nodes in the tree,
     * so we'll have to divide and conquer this tree,
     * we need to have two nodes to as the intermediate result,
     * also, refer to my earlier drawings:http://www.fishercoder.com/2016/06/23/lowest-common-ancestor-of-a-binary-tree/
     * I'm really impressed with myself at that time!*/

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

}

@@ -841,16 +841,68 @@
 6 %7B%0A
-%0A    /**
+    public static class Solution1 %7B%0A%0A        /**%0A         * 
 We n
@@ -932,24 +932,28 @@
 n the tree,%0A
+    
      * so we
@@ -999,16 +999,20 @@
 e,%0A     
+    
 * we nee
@@ -1062,16 +1062,20 @@
 result,%0A
+    
      * a
@@ -1192,16 +1192,20 @@
 e/%0A     
+    
 * I'm re
@@ -1248,16 +1248,26 @@
 ime!
+%0A         
 */%0A%0A    
 publ
@@ -1258,24 +1258,28 @@
     */%0A%0A    
+  
+  
 public TreeN
@@ -1348,24 +1348,28 @@
 ) %7B%0A        
+    
 if (root == 
@@ -1406,32 +1406,36 @@
 ) %7B%0A            
+  
+  
 return root;%0A   
@@ -1439,26 +1439,32 @@
         
-%7D%0A
+    %7D%0A  
         
 TreeNode
@@ -1447,32 +1447,34 @@
     %7D%0A          
+  
 TreeNode left = 
@@ -1504,32 +1504,36 @@
 ot.left, p, q);%0A
+    
         TreeNode
@@ -1585,24 +1585,28 @@
 q);%0A        
+  
+  
 if (left != 
@@ -1634,32 +1634,36 @@
 ) %7B%0A            
+    
 return root;%0A   
@@ -1659,34 +1659,42 @@
 n root;%0A        
+  
-%7D%0A
+  %7D%0A    
         return l
@@ -1721,16 +1721,26 @@
  right;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 236