¹«¹²¸¸½Úµã

/**
 * node A and node B, to get the closest common parent node. 
 *
 */
public class CommonParent {
 public Stack stack = new Stack();

 
 public Node getCommonParent(Node root, Node a, Node b) throws Exception{
  assert(root != null);
  assert(a != null);
  assert(b != null);
  
  Node node = find(root, a, b);
  if(node == null){
   throw new Exception("cannot find a or b.");
  }
  Node target = null;
  if(node.value == a.value){
   target = b;
  }
  if(node.value == b.value){
   target = a;
  }
  boolean result = dfs(node, target);
  if(result){
   //throw new Exception("can not find target : " + target.value);
   System.out.println("Found it, the common parent is : " + node.value);
   return node;
  }
  while(!stack.isEmpty()){
   Node parent = (Node) stack.pop();
   if(parent.right != null){
    result = dfs(parent.right, target);
    if(result){
     System.out.println("Found it, the common parent is : " + parent.value);
     return parent;
    }
   }

  }
  if(!result){
   throw new Exception("can not find the other node");
  }
  return null;
 }
 
 
 private Node find(Node parent, Node a, Node b) throws Exception {
  assert(true);
  Node node = null;
  stack.push(parent);
  if((parent.value==a.value) || (parent.value==b.value)){
   stack.pop();
   return parent;
  }
  if(parent.left != null){
   node = find(parent.left, a, b);
   if(node != null){
    return node;
   }
  }
  if(parent.right != null){
   node = find(parent.right, a, b);
   if(node != null){
    return node;
   }
  }
  stack.pop();
  return null;
 }
 
 private boolean dfs(Node node, Node target){
  assert(true);
  boolean b = false;
  if(node.value == target.value){
   return true;
  }
  if(node.left != null){
   b = b || dfs(node.left, target);
  }
  if(node.right != null){
   b = b || dfs(node.right, target);
  }
  
  return b;
 }
 /**
  * @param args
  */
 public static void main(String[] args) {
  BinaryTree bt = new BinaryTree();
  int[] array = {5,3,7,1,9,6,2,8,4};
  bt.buildTree(array);
  bt.printTree();

  CommonParent cp = new CommonParent();
  Node a = new Node(3);
  Node b = new Node(6);
  try {
   cp.getCommonParent(bt.root, a, b);
  } catch (Exception e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
 }

}