这里的二叉树不一定是二叉搜索树。
可以将其结构表示为 -
struct node {
int data;
struct node *left;
struct node *right;
};
其中序遍历结果为：8，4，9，2，5，1，6，3，7
后序遍历结果为：8，9，4，5，2，6，7，3，1
例如，如果我们要找到节点8和5的公共祖先，则需要在中序遍历时列出所有位于8和5之间的节点，而在此示例中，它们是[4，9，2]。然后我们检查此列表中最后出现在后序遍历中的节点，即2。因此，8和5的公共祖先是2。
我认为该算法的复杂度为O（n）（中序/后序遍历的O（n），其余步骤再次为O（n），因为它们仅是数组中的简单迭代）。但很有可能我错了。:-)
但这只是一个非常粗略的方法，我不确定是否有一些情况会失效。还有其他（可能更优）的解决方案吗？
解决方案1：递归 - 更快
- 时间复杂度：O(n)
- 空间复杂度：O(h) - 用于递归调用堆栈
class Solution
{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
if(root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null)
return right;
else if(right == null)
return left;
else
return root; // If(left != null && right != null)
}
}
解决方案2：迭代 - 使用父指针 - 较慢
- 时间复杂度：O(n) - 在最坏的情况下，我们可能会访问二叉树的所有节点。
- 空间复杂度：O(n) - 父指针哈希表、祖先集合和队列所使用的空间分别为O(n)。
class Solution
{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
HashSet<TreeNode> ancestors_set = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
parent_map.put(root, null);
queue.add(root);
while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
{
TreeNode node = queue.poll();
if(node.left != null)
{
parent_map.put(node.left, node);
queue.add(node.left);
}
if(node.right != null)
{
parent_map.put(node.right, node);
queue.add(node.right);
}
}
while(p != null)
{
ancestors_set.add(p);
p = parent_map.get(p);
}
while(!ancestors_set.contains(q))
q = parent_map.get(q);
return q;
}
}
这是 Php 代码。我假设树是一个数组二叉树。因此，您甚至不需要树来计算 LCA。 输入：两个节点的索引 输出：LCA 的索引
<?php
global $Ps;
function parents($l,$Ps)
{
if($l % 2 ==0)
$p = ($l-2)/2;
else
$p = ($l-1)/2;
array_push($Ps,$p);
if($p !=0)
parents($p,$Ps);
return $Ps;
}
function lca($n,$m)
{
$LCA = 0;
$arr1 = array();
$arr2 = array();
unset($Ps);
$Ps = array_fill(0,1,0);
$arr1 = parents($n,$arr1);
unset($Ps);
$Ps = array_fill(0,1,0);
$arr2 = parents($m,$arr2);
if(count($arr1) > count($arr2))
$limit = count($arr2);
else
$limit = count($arr1);
for($i =0;$i<$limit;$i++)
{
if($arr1[$i] == $arr2[$i])
{
$LCA = $arr1[$i];
break;
}
}
return $LCA;//this is the index of the element in the tree
}
var_dump(lca(5,6));
?>
如果有任何不足之处，请告诉我。
//如果两个值都小于当前节点，则遍历左子树 //或者如果两个值都大于当前节点，则遍历右子树 //否则，LCA就是当前节点
public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){
BSTNode commonAncestor = null;
if (currentRoot == null) {
System.out.println("The Tree does not exist");
return null;
}
int currentNodeValue = currentRoot.getValue();
//If both the values are less than the current node then traverse the left subtree
//Or If both the values are greater than the current node then traverse the right subtree
//Or LCA is the current node
if (a < currentNodeValue && b < currentNodeValue) {
commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b);
} else if (a > currentNodeValue && b > currentNodeValue) {
commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b);
} else {
commonAncestor = currentRoot;
}
return commonAncestor;
}
public class LeastCommonAncestor {
private TreeNode root;
private static class TreeNode {
TreeNode left;
TreeNode right;
int item;
TreeNode (TreeNode left, TreeNode right, int item) {
this.left = left;
this.right = right;
this.item = item;
}
}
public void createBinaryTree (Integer[] arr) {
if (arr == null) {
throw new NullPointerException("The input array is null.");
}
root = new TreeNode(null, null, arr[0]);
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
final int half = arr.length / 2;
for (int i = 0; i < half; i++) {
if (arr[i] != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (arr[left] != null) {
current.left = new TreeNode(null, null, arr[left]);
queue.add(current.left);
}
if (right < arr.length && arr[right] != null) {
current.right = new TreeNode(null, null, arr[right]);
queue.add(current.right);
}
}
}
}
private static class LCAData {
TreeNode lca;
int count;
public LCAData(TreeNode parent, int count) {
this.lca = parent;
this.count = count;
}
}
public int leastCommonAncestor(int n1, int n2) {
if (root == null) {
throw new NoSuchElementException("The tree is empty.");
}
LCAData lcaData = new LCAData(null, 0);
// foundMatch (root, lcaData, n1, n2);
/**
* QQ: boolean was returned but never used by caller.
*/
foundMatchAndDuplicate (root, lcaData, n1, n2, new HashSet<Integer>());
if (lcaData.lca != null) {
return lcaData.lca.item;
} else {
/**
* QQ: Illegal thrown after processing function.
*/
throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
}
}
// /**
// * Duplicate n1, n1 Duplicate in Tree
// * x x => succeeds
// * x 1 => fails.
// * 1 x => succeeds by throwing exception
// * 1 1 => succeeds
// */
// private boolean foundMatch (TreeNode node, LCAData lcaData, int n1, int n2) {
// if (node == null) {
// return false;
// }
//
// if (lcaData.count == 2) {
// return false;
// }
//
// if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
// lcaData.count++;
// return true;
// }
//
// boolean foundInCurrent = false;
// if (node.item == n1 || node.item == n2) {
// lcaData.count++;
// foundInCurrent = true;
// }
//
// boolean foundInLeft = foundMatch(node.left, lcaData, n1, n2);
// boolean foundInRight = foundMatch(node.right, lcaData, n1, n2);
//
// if ((foundInLeft && foundInRight) || (foundInCurrent && foundInRight) || (foundInCurrent && foundInLeft)) {
// lcaData.lca = node;
// return true;
// }
// return foundInCurrent || (foundInLeft || foundInRight);
// }
private boolean foundMatchAndDuplicate (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) {
if (node == null) {
return false;
}
// when both were found
if (lcaData.count == 2) {
return false;
}
// when only one of them is found
if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
if (!set.contains(node.item)) {
lcaData.count++;
return true;
}
}
boolean foundInCurrent = false;
// when nothing was found (count == 0), or a duplicate was found (count == 1)
if (node.item == n1 || node.item == n2) {
if (!set.contains(node.item)) {
set.add(node.item);
lcaData.count++;
}
foundInCurrent = true;
}
boolean foundInLeft = foundMatchAndDuplicate(node.left, lcaData, n1, n2, set);
boolean foundInRight = foundMatchAndDuplicate(node.right, lcaData, n1, n2, set);
if (((foundInLeft && foundInRight) ||
(foundInCurrent && foundInRight) ||
(foundInCurrent && foundInLeft)) &&
lcaData.lca == null) {
lcaData.lca = node;
return true;
}
return foundInCurrent || (foundInLeft || foundInRight);
}
public static void main(String args[]) {
/**
* Binary tree with unique values.
*/
Integer[] arr1 = {1, 2, 3, 4, null, 6, 7, 8, null, null, null, null, 9};
LeastCommonAncestor commonAncestor = new LeastCommonAncestor();
commonAncestor.createBinaryTree(arr1);
int ancestor = commonAncestor.leastCommonAncestor(2, 4);
System.out.println("Expected 2, actual " + ancestor);
ancestor = commonAncestor.leastCommonAncestor(2, 7);
System.out.println("Expected 1, actual " +ancestor);
ancestor = commonAncestor.leastCommonAncestor(2, 6);
System.out.println("Expected 1, actual " + ancestor);
ancestor = commonAncestor.leastCommonAncestor(2, 1);
System.out.println("Expected 1, actual " +ancestor);
ancestor = commonAncestor.leastCommonAncestor(3, 8);
System.out.println("Expected 1, actual " +ancestor);
ancestor = commonAncestor.leastCommonAncestor(7, 9);
System.out.println("Expected 3, actual " +ancestor);
// duplicate request
try {
ancestor = commonAncestor.leastCommonAncestor(7, 7);
} catch (Exception e) {
System.out.println("expected exception");
}
/**
* Binary tree with duplicate values.
*/
Integer[] arr2 = {1, 2, 8, 4, null, 6, 7, 8, null, null, null, null, 9};
commonAncestor = new LeastCommonAncestor();
commonAncestor.createBinaryTree(arr2);
// duplicate requested
ancestor = commonAncestor.leastCommonAncestor(8, 8);
System.out.println("Expected 1, actual " + ancestor);
ancestor = commonAncestor.leastCommonAncestor(4, 8);
System.out.println("Expected 4, actual " +ancestor);
ancestor = commonAncestor.leastCommonAncestor(7, 8);
System.out.println("Expected 8, actual " +ancestor);
ancestor = commonAncestor.leastCommonAncestor(2, 6);
System.out.println("Expected 1, actual " + ancestor);
ancestor = commonAncestor.leastCommonAncestor(8, 9);
System.out.println("Expected 8, actual " +ancestor); // failed.
}
}