_236.java

package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**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, inspired by this one: https://discuss.leetcode.com/topic/18566/my-java-solution-which-is-easy-to-understand
    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;
    }

}