Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

CC150-4.7.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree.
	 * Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
	 * 
	 * Solution:
	 * when p is one ancestor of q's, we say p is the first common ancestor of p, q
	 * Recursion to solve this problem
	 * Case 1: p, q locate in different side of root, first common ancestor must be root
	 * Case 2: p, q locates in same side of root
	 *         sub-case-1: p,q both in left of root , focus on left subtree and recurse on it
	 *         sub-case-2: p,q both in right of root, focus on right subtree and recurse on it
                      判断p, q 在不在某subtree也用到了recursion，做的时候没想到，看了答案才知道的
                      整道题就是逻辑＋递归，代码量很少，想着费脑
	 * 
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(H) for recursion calls
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		
	TreeNode root = new TreeNode(7);
        root.left = new TreeNode(10);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(1);
        root.right.left = new TreeNode(8);
        root.right.left.left = new TreeNode(11);
        TreeNode result=so.commonAncestor(root, root.right.left, root.right.left.left);
        System.out.println(result.val);
		
	}
	public TreeNode commonAncestor(TreeNode root,TreeNode p,TreeNode q){
		//如果p或者q在树中不存在
		if(!covers(root,p)||!covers(root,q))
			return null;
		return commonAncestorHelper(root,p,q);
	}
	private TreeNode commonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) {
		// TODO Auto-generated method stub
		if(root==null)
			return null;
		if(root==p||root==q)
			return root;
		// Let's check if they are in the same subtree
		boolean is_p_on_left=covers(root.left,p);
		boolean is_q_on_left=covers(root.left,q);
		if(is_p_on_left!=is_q_on_left)
			return root;
		//Else, they are on the same side. Traverse it.
		TreeNode childSide=is_p_on_left?root.left:root.right;
		return commonAncestorHelper(childSide, p, q);
	}
	private boolean covers(TreeNode root, TreeNode q) {
		// TODO Auto-generated method stub
		if(root==null)
			return false;
		if(root==q)
			return true;
		return covers(root.left,q)||covers(root.right,q);
	}
	
}