|
题目：求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。
package TestProblem;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Test50 {
/*
* 树的结点定义
*/
private static class TreeNode{
int val;
List<TreeNode> children=new LinkedList<>();//申请空间。链表
public TreeNode(){
}
public TreeNode(int val){
this.val=val;
}
@Override
public String toString(){
return val+"";
}
}
/**
* 找树中两个结点的最低公共祖先
* @param root 树的根结点
* @param p1 结点1
* @param p2 结点2
* @return 公共结点，没有返回null
*/
public static TreeNode getLastCommonParent(TreeNode root,TreeNode p1,TreeNode p2){
if(root==null||p1==null||p2==null){
return null;
}
List<TreeNode> path1=new LinkedList<>();
getNodePath(root, p1, path1);//找到含有目标结点的从头到尾的路径
List<TreeNode> path2=new LinkedList<>();
getNodePath(root, p2, path2);
return getLastCommonNode(path1, path2);//找出两条路径的公共结点
}
/**
* 找结点的路径
*
* @param root 根结点
* @param target 目标结点
* @param path 从根结点到目标结点的路径
*/
public static void getNodePath(TreeNode root,TreeNode target,List<TreeNode> path){
if(root==null){
return ;
}
path.add(root);
List<TreeNode> chrildren=root.children;
//处理子节点
for (TreeNode node:chrildren) {
if(node==target){
path.add(node);
return;
}else{
getNodePath(node, target, path);//递归寻找路径
}
}
//现场还原
path.remove(path.size()-1);
}
/**
* 找两个路径中的最后一个共同的结点
*
* @param p1 路径1
* @param p2 路径2
* @return 共同的结点，没有返回null
*/
public static TreeNode getLastCommonNode(List<TreeNode> p1,List<TreeNode> p2){
Iterator<TreeNode> ite1=p1.iterator();
Iterator<TreeNode> ite2=p2.iterator();//遍历两条路径
TreeNode last=null;
while(ite1.hasNext()&&ite2.hasNext()){
TreeNode tmp=ite1.next();//循环比较
if(tmp==ite2.next()){
last=tmp;//从上往下找到最后的一个公共结点即就是最低公共祖先
}
}
return last;
}
public static void main(String[] args) {
test01();
}
// 形状普通的树
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
public static void test01() {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
TreeNode n10 = new TreeNode(10);
n1.children.add(n2);
n1.children.add(n3);
n2.children.add(n4);
n4.children.add(n6);
n4.children.add(n7);
n3.children.add(n5);
n5.children.add(n8);
n5.children.add(n9);
n5.children.add(n10);//生成一棵树
System.out.println(getLastCommonParent(n1, n6, n8));
}
}
| 
转播
