将解决方案扩展到通用二叉树树的关键似乎在于找到连接根节点和目标节点的路径.获得此路径后,您可以轻松修改LCA功能以找到最低共同祖先.
下面的粗略实现使用java.util.concurrent.*中的LinkedBlockingQueue和java.util.*中的Stack – 但是,任何其他普通队列和堆栈也可以使用.该代码假定目标节点存在于树中.
public static void findPath2(Node target,Node top, Stack path){
LinkedBlockingQueue q1 = new LinkedBlockingQueue(), q2 = new LinkedBlockingQueue(),
q3 = new LinkedBlockingQueue();
Node n = top;
Node parrent = null;
while(n.getData().compareTo(target.getData())!= 0){
parrent = n;
if(n.right != null){
q2.add(n.right);
q3.add(parrent);
}
if(n.left != null){
q2.add(n.left);
q3.add(parrent);
}
n = q2.remove();
q1.add(n);
}
Stack s3 = new Stack(), s2 = new Stack();
while(!q3.isEmpty()){
s3.push(q3.remove());
}
for(int i = 1; i <= q2.size(); i++)
s3.pop();
while(!s3.isEmpty())
s2.push(s3.pop());
while(!q1.isEmpty())
s3.push(q1.remove());
LinkedBlockingQueue temp = new LinkedBlockingQueue();
while(!s2.isEmpty())
temp.add(s2.pop());
while(!temp.isEmpty())
s2.push(temp.remove());
path.push(s3.pop());
path.push(s2.pop());
while(!s3.isEmpty()){
n = s3.peek();
while(n.getData().compareTo(path.peek().getData()) != 0 && !s3.isEmpty()){
s3.pop();
s2.pop();
if(!s3.isEmpty())
n = s3.peek();
}
if(!s3.isEmpty()){
s3.pop();
path.push(s2.pop());
}
}
}
| 
转播
