logo标签列表

二叉树的最近公共祖先

javabinary-tree
13

这是一道常见的面试问题，唯一能找到关于此话题的内容是来自TopCoder的文章。但就面试答案来说，从我个人角度看，它看起来过于复杂。

有没有比通过绘制两个节点之间的路径并推断其祖先更简单的方法呢？（这是一个常见回答，但有一种变化的面试问题要求给出一个常数空间复杂度的答案）。

6个回答
11

一个简化版（但涉及较少）可以简单地是以下代码（我是.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;
    }
}
谢谢Mirko，但是有一个父指针使问题变得微不足道。我犯了错误 - 我忘了在问题中提到这一点。非常感谢您的解决方案 :) - user183037
非常好的解决方案....虽然使用了父指针.....不明白为什么它没有被接受！！ - Amol Sharma
2
文章提出的解决方案更加复杂的主要原因是它处理了一个两阶段的问题——预处理和查询，而从你的问题中可以看出你只做了一个查询，所以预处理没有意义。此外，它处理的是任意树而不是二叉树。
最好的答案肯定取决于树的细节。对于许多种树来说，时间复杂度将是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;
}

"constant-space"周围的引号是因为通常我们需要O(log(h))的空间来存储高度和它们之间的差异（比如，3个大整数）。但是，如果你正在处理高度太大无法塞入long类型的树，则可能有其他更紧迫的问题需要解决，这时存储几个节点的高度就不那么重要了。
如果您有一个二叉搜索树（BST），那么可以轻松地选择一个公共祖先（通常从根开始），并检查其子节点，看看它们是否是公共祖先：
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;
 }
}

如Philip JF所述，这个想法可以在任何树中用于常数空间算法，但对于一般的树来说，这样做会非常慢，因为反复确定CA.left或CA.right是否是公共祖先会重复很多工作，因此通常会选择使用更多的空间来节省时间。实现这种权衡的主要方法基本上就是你提到的算法（存储从根节点到目标节点的路径）。
谢谢 - 是的，我并不打算在这种特定情况下进行预处理。 - user183037
2

常数空间解法：（虽然不一定高效）。

有一个函数findItemInPath（int index，int searchId，Node root）

然后从树的深度为0的地方开始迭代，在搜索路径中找到第0项、第1项等等。

当您找到i使得该函数对于两者返回相同的结果，但对于i+1则不是，则路径中的第i项是最低公共祖先。

谢谢，我认为这是一个好主意。我们可能还需要在函数中添加另一个参数来说明每一步的父节点是什么，以便我们能够在第(i+1)次调用中发现不同的结果时立即打印出它。听起来很不错 - 再次感谢！ - user183037
我认为这种方法只有作为一种智力练习才有用，因为时间复杂度是O(N)，除非已排序且平衡，在这种情况下时间复杂度为O(log(n))。但是，对于这个问题的自然算法使用O(log(N))空间，并且可以通过修改下面的代码来基于键值搜索树（选择左子树或右子树）而不仅仅是前缀顺序（先搜索左边再搜索右边）。 - Larry Watanabe
1

显而易见的解决方案是使用log(n)空间（n是节点数）的算法，这就是你提到的算法。以下是一个实现。在最坏情况下，它需要O(n)时间（想象一下你正在搜索共同祖先的其中一个节点包括最后一个节点的情况）。

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);
        }
    }
}
谢谢，我选择了你的另一个解决方案，因为它使用恒定的空间。 - user183037
它可能使用恒定的空间，但我认为在恒定的空间内高效实现会很困难。例如，如何找到到达ID的路径上的第一个元素？答案是搜索左子树或右子树，然后选择适当的子树。但搜索子树需要O（N）时间，因此这将花费约O（N * 2）的时间。 - Larry Watanabe
我认为关于常数空间答案的问题有点像是一个诡计问题。你应该说：“是的，有一个常数空间答案（描述我上面的答案），但它是不切实际的，因为它需要O(N*2)的时间，所以最好使用上面的解决方案，它是O(N)，并且可以通过平衡和排序树轻松改进为O(log(N))。” - Larry Watanabe
1

使用的树的类型很重要。您始终可以在常量空间内确定节点是否是另一个节点的祖先，并且顶部节点始终是公共祖先，因此在常量空间中获取最低公共祖先只需要迭代向下即可。在二叉搜索树上，这很容易快速完成，但在任何树上都可以工作。

对于这个问题，许多不同的权衡是相关的，而树的类型则很重要。如果您具有指向父节点而不仅仅是子节点的指针，则该问题会更容易（Mirko的代码使用了这种方法）

另请参见： http://en.wikipedia.org/wiki/Lowest_common_ancestor

0

此处描述的自底向上方法是一种O(n)时间，O(1)空间的方法：here

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
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接