非二叉树中最近公共管理者（LCM）代码问题修复求助

问题背景 #

我需要在非二叉树中找到两个节点的最近公共管理者（LCM），用二叉树做简化演示：

• 传入节点H和I时，正确返回E；
• 传入节点D和I时，正确返回B。
  当前代码多数情况正常，但传入节点I和L时，代码返回I，而我预期返回E，该如何修复？

原代码 #

class Node
{
    public string Name { get; set; }
    public List<Node> Children { get; set; }
    public Node(string name)
    {
        Name = name;
        Children = new List<Node>();
    }
}
class CommonManager
{
    public static Dictionary<string, Node> dictionary;

    public CommonManager()
    {
        dictionary = new Dictionary<string, Node>();
        Node root = new Node("A");
        root.Children.Add(new Node("B"));
        //root.Children.Add(new Node("C"));
        //root.Children.Add(new Node("AA"));
        root.Children[0].Children.Add(new Node("D"));
        root.Children[0].Children.Add(new Node("E"));
        //root.Children[1].Children.Add(new Node("F"));
        //root.Children[1].Children.Add(new Node("G"));
        root.Children[0].Children[1].Children.Add(new Node("H"));
        root.Children[0].Children[1].Children.Add(new Node("I"));
        //root.Children[1].Children[0].Children.Add(new Node("J"));
        //root.Children[1].Children[0].Children.Add(new Node("K"));
        root.Children[0].Children[1].Children[1].Children.Add(new Node("L"));

        Node n1 = root.Children[0].Children[1].Children[1].Children[0];//L
        Node n2 = root.Children[0].Children[1].Children[1];//I

        Node lcm = FindLCM(root, n1, n2);
        if (lcm != null)
            Console.WriteLine("The LCM is " + lcm.Name);
        else
            Console.WriteLine("No LCM found.");

        Console.ReadKey();
    }

    static Node FindLCM(Node root, Node n1, Node n2)
    {
        if (root == null)
            return null;

        //If selected node is n1 or n2 return node. 
        if (root == n1 || root == n2)
            return root;

        Node lcm = null;
        int count = 0;
        //Use debug > Windows > Parallel Watch to track variables. 
        foreach (Node child in root.Children)
        {
            Console.WriteLine(child.Name);
            Node temp = FindLCM(child, n1, n2);
            if (temp != null)
            {
                lcm = temp;
                Console.WriteLine("temp.Name:--> " + temp.Name);
                count++;
            }
        }

        if (count == 2)
            return root;
        else
            return lcm;
    }
}

问题原因 #

按常规LCM定义，I是L的直接父节点，I和L的最近公共管理者就是I，代码返回的结果是正确的。如果你确实需要返回E，说明你的需求是LCM不能是目标节点本身，必须是两个节点的上层公共祖先。

当前代码的逻辑漏洞在于：当遍历到目标节点（比如I）时，会直接返回该节点，不会继续遍历它的子节点，因此无法发现该节点的子树中存在另一个目标节点（L）。此时count始终为1，最终返回的是先匹配到的目标节点，而非你预期的上层祖先。

修复方案 #

修改递归逻辑，不直接返回目标节点，而是先遍历所有子节点，统计子树中包含目标节点的数量，再结合当前节点是否为目标节点来判断：

static Node FindLCM(Node root, Node n1, Node n2)
{
    if (root == null)
        return null;

    int count = 0;
    Node result = null;

    // 先遍历所有子节点，收集子树中的匹配情况
    foreach (Node child in root.Children)
    {
        Node temp = FindLCM(child, n1, n2);
        if (temp != null)
        {
            count++;
            result = temp;
        }
    }

    // 判断当前节点是否是目标节点之一
    bool isTarget = root == n1 || root == n2;
    if (isTarget)
    {
        count++;
    }

    // 两种情况返回当前节点：
    // 1. 当前节点是目标节点，且子树中存在另一个目标节点（count=2）
    // 2. 子树中有两个不同的目标节点（count=2）
    if (count == 2)
    {
        return root;
    }

    // 如果当前节点是目标节点，返回自己；否则返回子树中的匹配结果
    return isTarget ? root : result;
}

修复后逻辑说明 #

• 遍历所有子节点，统计子树中包含目标节点的数量；
• 若当前节点是目标节点，计数加1；
• 当计数为2时，说明当前节点就是两个目标节点的最近公共管理者（不管当前节点是否是目标节点）；
• 若当前节点是目标节点且计数为1，返回当前节点（符合常规LCM定义）；若需要强制排除自身作为LCM，可在此处调整逻辑（比如返回null，让上层节点继续判断）。

如果你的需求确实是LCM不能是目标节点本身，可以进一步修改：当当前节点是目标节点且计数为1时，返回null，这样上层节点会捕获到子树中存在目标节点，最终返回上层的公共祖先。修改后的对应代码段：

// 如果当前节点是目标节点，返回null（让上层节点处理）；否则返回子树中的匹配结果
return isTarget ? null : result;

内容的提问来源于stack exchange，提问作者OpenStack