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;
    }

}

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 {
    public static class Solution1 {

        /**
         * 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;
        }
    }

}

refactor 236