题目：求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。
代码如下：
package demo;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* 树中两个结点的最低公共祖先。 此树不是二叉树，并且没有指向父结点的指针。
*
* @author xiangdonglee
*
*/
public class Test50 {
/**
* 树的结点定义
*
* @author xiangdonglee
*
*/
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 target
* 目标结点
* @param path
* 根结点到目标结点的路径
*/
public static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> path) {
if (root == null) {
return;
}
// 添加当前结点
path.add(root);
List<TreeNode> children = root.children;
// 处理子结点
for (TreeNode node : children) {
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> it1 = p1.iterator();
Iterator<TreeNode> it2 = p2.iterator();
TreeNode last = null;
while (it1.hasNext() && it2.hasNext()) {
TreeNode tmp = it1.next();
if (tmp == it2.next()) {
last = tmp;
}
}
return last;
}
/**
* 找树中两个结点的最低公共祖先
*
* @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);
}
public static void main(String[] args) {
test1();
System.out.println("===========");
test2();
System.out.println("===========");
test3();
}
/**
* 形状普通的树
*/
private static void test1() {
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);
n3.children.add(n5);
n4.children.add(n6);
n4.children.add(n7);
n5.children.add(n8);
n5.children.add(n9);
n5.children.add(n10);
System.out.println(getLastCommonParent(n1, n6, n8));
}
/**
* 树退化成一个链表
*/
private static void test2() {
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);
n1.children.add(n2);
n2.children.add(n3);
n3.children.add(n4);
n4.children.add(n5);
System.out.println(getLastCommonParent(n1, n4, n5));
}
/**
* 树退化成一个链表，一个结点不在树中
*/
private static void test3() {
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);
n1.children.add(n2);
n2.children.add(n3);
n3.children.add(n4);
n4.children.add(n5);
System.out.println(getLastCommonParent(n1, n5, n6));
}
}
运行结果
test1()
test2()
test3()
