java - 二叉树的最低公共(public)祖先

Question

这是一个很受欢迎的面试问题，我能找到的关于该主题的唯一一篇文章来自 TopCoder .不幸的是，从面试答案的角度来看，它看起来过于复杂。

除了绘制到两个节点的路径并推导祖先之外，是否有更简单的方法来执行此操作？ (这是一个流行的答案，但面试问题的变体要求一个恒定的空格答案)。

Answer 1

一个简单化的(但较少涉及的版本)可以简单地是(这里的 .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;
    }
}