Это популярный вопрос для интервью, и единственная статья, которую я могу найти по этой теме, - это один из TopCoder. К сожалению, для меня это выглядит слишком сложно с точки зрения интервью.
Нет ли более простого способа сделать это иначе, чем проложить путь к обоим узлам и вывести предка? (Это популярный ответ, но есть вариант ответа на вопрос, требующий ответа на постоянный пробел).
Ответ на постоянное пространство: (хотя и не обязательно эффективный).
Есть функция findItemInPath (int index, int searchId, Node root)
то итерация от 0.. глубины дерева, поиск 0-го элемента, 1-го элемента и т.д. в обоих путях поиска.
Когда вы найдете я так, чтобы функция возвращала тот же результат для обоих, но не для я + 1, то i-й элемент в пути является самым низким общим предком.
Простейшая (но гораздо менее используемая версия) может быть просто (.NET парень здесь Java немного ржавый, поэтому, пожалуйста, извините синтаксис, но я думаю, вам не придется слишком много настраивать). Это то, что я бросил вместе.
class Program
{
static void Main(string[] args)
{
Node node1 = new Node { Number = 1 };
Node node2 = new Node { Number = 2, Parent = node1 };
Node node3 = new Node { Number = 3, Parent = node1 };
Node node4 = new Node { Number = 4, Parent = node1 };
Node node5 = new Node { Number = 5, Parent = node3 };
Node node6 = new Node { Number = 6, Parent = node3 };
Node node7 = new Node { Number = 7, Parent = node3 };
Node node8 = new Node { Number = 8, Parent = node6 };
Node node9 = new Node { Number = 9, Parent = node6 };
Node node10 = new Node { Number = 10, Parent = node7 };
Node node11 = new Node { Number = 11, Parent = node7 };
Node node12 = new Node { Number = 12, Parent = node10 };
Node node13 = new Node { Number = 13, Parent = node10 };
Node commonAncestor = FindLowestCommonAncestor(node9, node12);
Console.WriteLine(commonAncestor.Number);
Console.ReadLine();
}
public class Node
{
public int Number { get; set; }
public Node Parent { get; set; }
public int CalculateNodeHeight()
{
return CalculateNodeHeight(this);
}
private int CalculateNodeHeight(Node node)
{
if (node.Parent == null)
{
return 1;
}
return CalculateNodeHeight(node.Parent) + 1;
}
}
public static Node FindLowestCommonAncestor(Node node1, Node node2)
{
int nodeLevel1 = node1.CalculateNodeHeight();
int nodeLevel2 = node2.CalculateNodeHeight();
while (nodeLevel1 > 0 && nodeLevel2 > 0)
{
if (nodeLevel1 > nodeLevel2)
{
node1 = node1.Parent;
nodeLevel1--;
}
else if (nodeLevel2 > nodeLevel1)
{
node2 = node2.Parent;
nodeLevel2--;
}
else
{
if (node1 == node2)
{
return node1;
}
node1 = node1.Parent;
node2 = node2.Parent;
nodeLevel1--;
nodeLevel2--;
}
}
return null;
}
}
Основная причина, по которой статьи более сложны, заключается в том, что она имеет дело с двухэтапной задачей - предварительной обработкой, а затем запросами, - хотя из вашего вопроса это звучит так, будто вы делаете только один запрос, поэтому препроцессинг не делает смысл. Он также имеет дело с произвольными деревьями, а не с бинарными деревьями.
Лучший ответ, безусловно, зависит от деталей о дереве. Для многих видов деревьев временной сложностью будет O (h), где h - высота дерева. Если у вас есть указатели на родительские узлы, то легкое "постоянное пространство" ответ, как и в решении Mirko, позволяет найти высоту узлов и сравнить предков одинаковой высоты. Обратите внимание, что это работает для любого дерева с родительскими ссылками, двоичными или нет. Мы можем улучшить решение Mirko, сделав функцию высоты итеративной и разделив петли "добираемся до одной и той же глубины" из основного цикла:
int height(Node n){
int h=-1;
while(n!=null){h++;n=n.parent;}
return h;
}
Node LCA(Node n1, Node n2){
int discrepancy=height(n1)-height(n2);
while(discrepancy>0) {n1=n1.parent;discrepancy--;}
while(discrepancy<0) {n2=n2.parent;discrepancy++;}
while(n1!=n2){n1=n1.parent();n2=n2.parent();}
return n1;
}Кавычки вокруг "постоянного пространства" связаны с тем, что в общем случае нам нужно пространство O (log (h)) для хранения высот и разности между ними (скажем, 3 BigIntegers). Но если вы имеете дело с деревьями, высота которых слишком велика, чтобы занять много времени, вам, вероятно, придется беспокоиться о других проблемах, которые более насущны, чем сохранение высоты нескольких узлов.
Если у вас есть BST, вы можете легко взять общего предка (usu, начиная с root) и проверить его детей, чтобы увидеть, является ли один из них общим предком:
Node LCA(Node n1, Node n2, Node CA){
while(true){
if(n1.val<CA.val & n2.val<CA.val) CA=CA.left;
else if (n1.val>CA.val & n2.val>CA.val) CA=CA.right;
else return CA;
}
}Как упоминал Филипп Дж.Ф., эта же идея может быть использована в любом дереве для алгоритма с постоянным пространством, но для общего дерева, выполняющего его таким образом, будет очень медленным, так как неоднократно выясняется, являются ли CA.left или CA.right общий предок повторит много работы, поэтому вы обычно предпочитаете использовать больше места для экономии времени. Основным способом сделать этот компромисс будет в основном алгоритм, который вы упомянули (сохранение пути от root).
Неважно, какое дерево вы используете. Вы всегда можете указать, является ли node предком другого node в постоянном пространстве, а верхний node всегда является общим предком, поэтому получение минимального общего предка в постоянном пространстве просто требует итерации вашего пути вниз. В двоичном дереве поиска это довольно легко сделать быстро, но оно будет работать на любом дереве.
Для этой проблемы важны многие различные компромиссы, а тип дерева имеет значение. Проблема имеет тенденцию намного легче, если у вас есть указатели на родительские узлы, а не только на детей (это использует код Mirko)
См. также: http://en.wikipedia.org/wiki/Lowest_common_ancestor
Очевидным решением, использующим log (n) space, (n является число узлов), является упомянутый вами алгоритм. Вот реализация. В худшем случае требуется время O (n) (представьте, что один из node, который вы ищете для общего предка, включает в себя последний node).
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Node
{
private static int counter = 0;
private Node left = null;
private Node right = null;
public int id = counter++;
static Node constructTreeAux(int depth)
{
if (depth == 0)
return null;
Node newNode = new Node();
newNode.left = constructTree(depth - 1);
newNode.right = constructTree(depth - 1);
return newNode;
}
public static Node constructTree(int depth)
{
if (depth == 0)
return null;
Node root = new Node();
root.left = constructTreeAux(depth - 1);
root.right = constructTreeAux(depth - 1);
return root;
}
private List<Node> findPathAux(List<Node> pathSoFar, int searchId)
{
if (this.id == searchId)
{
if (pathSoFar == null)
pathSoFar = new List<Node>();
pathSoFar.Add(this);
return pathSoFar;
}
if (left != null)
{
List<Node> result = left.findPathAux(null, searchId);
if (result != null)
{
result.Add(this);
return result;
}
}
if (right != null)
{
List<Node> result = right.findPathAux(null, searchId);
if (result != null)
{
result.Add(this);
return result;
}
}
return null;
}
public static void printPath(List<Node> path)
{
if (path == null)
{
Console.Out.WriteLine(" empty path ");
return;
}
Console.Out.Write("[");
for (int i = 0; i < path.Count; i++)
Console.Out.Write(path[i] + " ");
Console.Out.WriteLine("]");
}
public override string ToString()
{
return id.ToString();
}
/// <summary>
/// Returns null if no common ancestor, the lowest common ancestor otherwise.
/// </summary>
public Node findCommonAncestor(int id1, int id2)
{
List<Node> path1 = findPathAux(null, id1);
if (path1 == null)
return null;
path1 = path1.Reverse<Node>().ToList<Node>();
List<Node> path2 = findPathAux(null, id2);
if (path2 == null)
return null;
path2 = path2.Reverse<Node>().ToList<Node>();
Node commonAncestor = this;
int n = path1.Count < path2.Count? path1.Count : path2.Count;
printPath(path1);
printPath(path2);
for (int i = 0; i < n; i++)
{
if (path1[i].id == path2[i].id)
commonAncestor = path1[i];
else
return commonAncestor;
}
return commonAncestor;
}
private void printTreeAux(int depth)
{
for (int i = 0; i < depth; i++)
Console.Write(" ");
Console.WriteLine(id);
if (left != null)
left.printTreeAux(depth + 1);
if (right != null)
right.printTreeAux(depth + 1);
}
public void printTree()
{
printTreeAux(0);
}
public static void testAux(out Node root, out Node commonAncestor, out int id1, out int id2)
{
Random gen = new Random();
int startid = counter;
root = constructTree(5);
int endid = counter;
int offset = gen.Next(endid - startid);
id1 = startid + offset;
offset = gen.Next(endid - startid);
id2 = startid + offset;
commonAncestor = root.findCommonAncestor(id1, id2);
}
public static void test1()
{
Node root = null, commonAncestor = null;
int id1 = 0, id2 = 0;
testAux(out root, out commonAncestor, out id1, out id2);
root.printTree();
commonAncestor = root.findCommonAncestor(id1, id2);
if (commonAncestor == null)
Console.WriteLine("Couldn't find common ancestor for " + id1 + " and " + id2);
else
Console.WriteLine("Common ancestor for " + id1 + " and " + id2 + " is " + commonAncestor.id);
}
}
}
Ниже описан подход ниже здесь - это O (n) время, O (1) космический подход:
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees
}