二叉树的最低共同祖先

Question

这是一个受欢迎的访谈问题,我可以在这个主题上找到的唯一一篇文章来自TopCoder.对我来说不幸的是,从面试答案的角度看,它看起来过于复杂.

除了绘制两个节点的路径并推断祖先之外,是否有更简单的方法可以做到这一点？(这是一个很受欢迎的答案,但是面试问题的变化需要一个恒定的空间答案).

Answer 1

一个简单的(但更少涉及的版本)可能只是(这里的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;
    }
}

Answer 2

恒定空间答案：（虽然不一定高效）。

有一个函数 findItemInPath(int index, int searchId, Node root)

然后从树的 0 .. 深度迭代，在两个搜索路径中查找第 0 个项目、第 1 个项目等。

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