代码语言：javascript复制
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);
}
}今天我遇到一个问题，问题描述如下：
寻找二叉树，两个节点的最低公共祖先，最低公共祖先意思是从下往上两个节点遇到的第一个祖先。
解决这个问题的思路有两种：
1.从根节点往下寻找，如果发现两个节点分别在左右子树上那么就找到了最低公共祖先，这是一个思路，但是这种算法实现起来复杂度比较高，所以放弃，选择第二种思路
2.第二种思路是，两个节点，分别找到，从根节点到这两个节点的路径，找到路径后问题就转变为求两个链表的交叉点，这样就好做多了，就是从根节点按照路径往下遍历，如果果首次发现两个链表的节点不是同一个节点了，那么两个链表上一个公共节点就是最低祖先，首先得问题就是怎么找到路径，我解决这个问题的方法是回溯法，新建一个类，这个类的成员变量有二叉树的节点，两个布尔型变量，代表左右子树是否被遍历过，false为没有遍历，true为已经遍历过了，还有一个变量就存放着走向，‘l’代表向左走，‘r’代表向右走，从根节点开始如果左子树没遍历过，就把左孩子压入栈，如果有右子树没有遍历，就把右孩子压入栈，下一轮循环中再以栈顶元素为当前节点查看条件，如果说左右子树都被遍历，那么就回溯，让栈顶元素出栈，如果找到元素，那么就返回，如果栈为空了，那么就证明没有找到，想要的节点。以下是我代码：
