题目：输入两个树节点，求它们的最低公共祖先。
参考答案
class TreeNode {
T value;
List> children;
public TreeNode(T value) {
this.value = value;
children = new ArrayList<>();
}
}
public TreeNode getLastCommonParent(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null || node1 == null || node2 == null) {
return null;
}
LinkedList> path1 = new LinkedList<>();
getNodePath(root, node1, path1);
LinkedList> path2 = new LinkedList<>();
getNodePath(root, node2, path2);
return getLastCommonNode(path1, path2);
}
private boolean getNodePath(TreeNode root, TreeNode node, LinkedList> path) {
if (root == node) {
return true;
}
path.add(root);
boolean found = false;
for (int i = 0; !found && i < root.children.size(); i++) {
found = getNodePath(root.children.get(i), node, path);
}
if (!found) {
path.removeLast();
}
return found;
}
private TreeNode getLastCommonNode(LinkedList> path1, LinkedList> path2) {
Iterator> iterator1 = path1.iterator();
Iterator> iterator2 = path2.iterator();
TreeNode last = null;
while (iterator1.hasNext() && iterator2.hasNext()) {
TreeNode node = iterator1.next();
if (node == iterator2.next()) {
last = node;
} else {
break;
}
}
return last;
}
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(logn)。
转播
