二叉树两个节点的最低公共最先问题

package com.test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 回溯法寻找路径问题
 * @author zhangteng
 *
 */
public class Main {

	static class Node{
		int data;
		Node left;
		Node right;
	    public Node(int data){
	    	this.data=data;
	    }
	}
	
	static class PathNode{
		Node pNode;
		boolean left=false;
		boolean right=false;
		char direct;
		public PathNode(Node pNode){
			this.pNode=pNode;
		}
	}
	private static Stack<PathNode> findPath(Node tree,Node purpose){
		Stack<PathNode> s=new Stack<PathNode>();
		
		Node now=tree;
		if(now==purpose){
			return null;
		}//初始化工作
		PathNode temp=new PathNode(now);
		temp.direct='l';
		if(now.left==null){
			temp.left=true;
			temp.direct='r';
		}
		if(now.right==null){
			if(temp.direct=='r'){
				temp.direct='e';
			}
			temp.right=true;
		}
		s.push(temp);
		while(s.peek().pNode!=purpose&&!s.isEmpty()){
		   if(s.peek().direct=='e'){
			   return s;
		   }
		   //System.out.println(s.peek().pNode.data);
		   if(!s.peek().left){
			  if(s.peek().pNode.left!=null){
				  now=s.peek().pNode.left;
				  s.peek().left=true;
				  s.peek().direct='l';
				  temp=new PathNode(now);
				  s.push(temp);
			  }else{
				  s.peek().left=true;
			  }
		   }else if(!s.peek().right){
			   if(s.peek().pNode.right!=null){
				   now=s.peek().pNode.right;
				   s.peek().right=true;
				   s.peek().direct='r';
				   temp=new PathNode(now);
				   s.push(temp);
			   }else{
				   s.peek().right=true;
			   }
		   }else if(s.peek().left&&s.peek().right){
			   s.pop();
		   }
		}
		//s.pop();
		return s;
	}
	
	public static List<Character> getPath(Node root,Node purpose){
		List<Character> list=new ArrayList<Character>();
		Stack<PathNode> st=findPath(root, purpose);
		if(st==null){
			//节点就是根节点所以没路径
			return list;
		}else if(st.size()==0){
			//没找到路径
			return null;
		}else{
			Stack<PathNode> temp=new Stack<PathNode>();
			while(!st.isEmpty()){
			   temp.push(st.pop());
			}
			while(!temp.isEmpty()){
				list.add(temp.pop().direct);
			}
			return list;
		}
	}
	
	public static Node getGradFather(Node root,Node p1,Node p2){
		//找到节点p1的路径
		List<Character> path1=getPath(root, p1);
		//找到节点p2的路径
		List<Character> path2=getPath(root, p2);
		if(path1==null||path2==null){
			//路径1或者路径2为空也就是没找到
			return null;
		}else if(path1.size()==0||path2.size()==0){
			//没有路径就代表是根节点所以最低最先一定是根节点
			return root;
		}else{
			List<Character> sharePath=new ArrayList<Character>();
			for(int i=0;path1.get(i)==path2.get(i);i++){
				sharePath.add(path1.get(i));
			}
			Node temp=root;
			for(int j=0;j<sharePath.size();j++){
				if(sharePath.get(j)=='l'){
					temp=temp.left;
				}else{
					temp=temp.right;
				}
			}
			return temp;
		}
	}
	public static void main(String[] args) {
		Node t1=new Node(1);
		Node t2=new Node(2);
		Node t3=new Node(3);
		Node t4=new Node(4);
		Node t5=new Node(5);
		Node t6=new Node(6);
		Node t7=new Node(7);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        t3.left=t6;
        t3.right=t7;
        
        System.out.print(getGradFather(t1, t1, t3).data);
	}

}