題目：求樹中兩個結(jié)點(diǎn)的最低公共祖先，此樹不是二叉樹，并且沒有指向父節(jié)點(diǎn)的指針攘已。
代碼如下：
package demo;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* 樹中兩個結(jié)點(diǎn)的最低公共祖先彬伦。 此樹不是二叉樹，并且沒有指向父結(jié)點(diǎn)的指針型凳。
*
* @author xiangdonglee
*
*/
public class Test50 {
/**
* 樹的結(jié)點(diǎn)定義
*
* @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 + "";
}
}
/**
* 找結(jié)點(diǎn)的路徑
*
* @param root
* 根結(jié)點(diǎn)
* @param target
* 目標(biāo)結(jié)點(diǎn)
* @param path
* 根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑
*/
public static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> path) {
if (root == null) {
return;
}
// 添加當(dāng)前結(jié)點(diǎn)
path.add(root);
List<TreeNode> children = root.children;
// 處理子結(jié)點(diǎn)
for (TreeNode node : children) {
if (node == target) {
path.add(node);
return;
} else {
getNodePath(node, target, path);
}
}
// 現(xiàn)場還原
path.remove(path.size() - 1);
}
/**
* 找兩個路徑中的最后一個共同的結(jié)點(diǎn)
*
* @param p1
* 路徑1
* @param p2
* 路徑2
* @return 共同的結(jié)點(diǎn)，沒有返回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;
}
/**
* 找樹中兩個結(jié)點(diǎn)的最低公共祖先
*
* @param root
* 樹的根結(jié)點(diǎn)
* @param p1
* 結(jié)點(diǎn)1
* @param p2
* 結(jié)點(diǎn)2
* @return 公共結(jié)點(diǎn)嘱函，沒有就返回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));
}
/**
* 樹退化成一個鏈表甘畅，一個結(jié)點(diǎn)不在樹中
*/
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));
}
}
運(yùn)行結(jié)果
test1()
test2()
test3()
