Lowest Common Ancestor

Source

• lintcode: Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common 
ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the 
ancestor of both nodes.

Example
For the following binary tree:

  4
 / \
3   7
   / \
  5   6
LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(!cover(root, p) || !cover(root, q)){
            return null;
        }
        return dfs(root, p, q);
    }

    public boolean cover(TreeNode root, TreeNode node){
        if(root==null) return false;
        if(root==node) return true;
        return cover(root.left, node) || cover(root.right, node);
    }

    public static TreeNode dfs(TreeNode root, TreeNode p, TreeNode q){
        if(root==null){
            return null;
        }
        if(root==q || root==p){
            return root;
        }
        TreeNode l = dfs(root.left, p, q);
        TreeNode r = dfs(root.right, p, q);
        if(l!=null && r!=null) return root;
        if(l!=null){
            return l;
        }
        return r;
    }
}