题目:输入两个树节点,求它们的最低公共祖先。
参考答案
class TreeNode<T> {
T value;
List<TreeNode<T>> children;
public TreeNode(T value) {
this.value = value;
children = new ArrayList<>();
}
}
public <T> TreeNode<T> getLastCommonParent(TreeNode<T> root, TreeNode<T> node1, TreeNode<T> node2) {
if (root == null || node1 == null || node2 == null) {
return null;
}
LinkedList<TreeNode<T>> path1 = new LinkedList<>();
getNodePath(root, node1, path1);
LinkedList<TreeNode<T>> path2 = new LinkedList<>();
getNodePath(root, node2, path2);
return getLastCommonNode(path1, path2);
}
private <T> boolean getNodePath(TreeNode<T> root, TreeNode<T> node, LinkedList<TreeNode<T>> 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 <T> TreeNode<T> getLastCommonNode(LinkedList<TreeNode<T>> path1, LinkedList<TreeNode<T>> path2) {
Iterator<TreeNode<T>> iterator1 = path1.iterator();
Iterator<TreeNode<T>> iterator2 = path2.iterator();
TreeNode<T> last = null;
while (iterator1.hasNext() && iterator2.hasNext()) {
TreeNode<T> node = iterator1.next();
if (node == iterator2.next()) {
last = node;
} else {
break;
}
}
return last;
}
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(logn)。
网友评论