C#二叉树最远/最近叶节点距离求解及代码优化求助

现有代码的核心问题 #

你当前的FindMaxSumPath代码是计算二叉树路径和的最大值，和需求的「叶节点间的距离」完全不匹配；而且additionsCount的逻辑也不符合预期——它只是记录了更新最大和的次数，并非叶节点间的距离。另外，ref参数可以通过返回多值的方式替代，不需要引用传递。

先明确需求里的「距离」定义：通常二叉树叶节点间的距离指的是两个叶节点之间路径的边数（若要按节点数计算，结果加1即可）。

一、移除ref参数，实现二叉树最远叶节点的最大距离（树的直径） #

树的直径是二叉树中任意两个叶节点间的最长路径，路径可能经过根节点，也可能不经过。我们用返回元组的方式，同时返回当前子树的最大深度（当前节点到最远叶节点的边数）和当前子树内的最大距离，彻底抛弃ref参数。

修正后的代码 #

// 二叉树节点定义（假设你的Element结构如下）
public class Element<T>
{
    public T Data { get; set; }
    public Element<T> Left { get; set; }
    public Element<T> Right { get; set; }
}

public class BinaryTree<T>
{
    private Element<T> Root { get; set; }

    // 内部递归方法，返回(当前子树最大深度, 当前子树内的最大距离)
    private (int MaxDepth, int MaxDistance) CalculateMaxDistance(Element<T> node)
    {
        if (node == null)
        {
            // 空节点深度为-1（边数统计逻辑），距离为0
            return (-1, 0);
        }

        var left = CalculateMaxDistance(node.Left);
        var right = CalculateMaxDistance(node.Right);

        // 当前节点的最大深度 = 左右子树最大深度的最大值 + 1（当前节点到子节点的边）
        int currentMaxDepth = Math.Max(left.MaxDepth, right.MaxDepth) + 1;
        // 当前节点作为路径中点的距离 = 左子树深度 + 右子树深度 + 2（左右子树到当前节点的两条边）
        int currentDistance = left.MaxDepth + right.MaxDepth + 2;
        // 当前子树的最大距离 = 左子树最大距离、右子树最大距离、当前路径距离的最大值
        int currentMaxDistance = Math.Max(Math.Max(left.MaxDistance, right.MaxDistance), currentDistance);

        return (currentMaxDepth, currentMaxDistance);
    }

    // 对外暴露的方法，返回最远叶节点间的最大距离
    public int FindMaxLeafDistance()
    {
        if (Root == null)
            return 0;
        var result = CalculateMaxDistance(Root);
        return result.MaxDistance;
    }
}

二、实现最近叶节点间的最小距离 #

最近叶节点的最小距离需考虑两种情况：

1. 两个叶节点在同一个子树内，最小距离为该子树内的最小叶节点距离
2. 两个叶节点分别在左右子树，距离为左子树最近叶节点深度 + 右子树最近叶节点深度 + 2（边数）

同样用返回元组的方式避免ref参数：

代码实现 #

public class BinaryTree<T>
{
    // 内部递归方法，返回(当前子树最近叶节点的深度, 当前子树内的最小叶节点距离)
    private (int MinDepth, int MinDistance) CalculateMinDistance(Element<T> node)
    {
        if (node == null)
        {
            // 空节点深度设为int.MaxValue（表示不可达），距离设为int.MaxValue
            return (int.MaxValue, int.MaxValue);
        }

        // 当前是叶节点
        if (node.Left == null && node.Right == null)
        {
            // 叶节点到自身深度为0，单个叶节点无距离，设为int.MaxValue
            return (0, int.MaxValue);
        }

        var left = CalculateMinDistance(node.Left);
        var right = CalculateMinDistance(node.Right);

        // 当前节点的最近叶节点深度 = 左右子树最近深度的最小值 + 1
        int currentMinDepth = Math.Min(left.MinDepth, right.MinDepth) + 1;
        int currentMinDistance = int.MaxValue;

        // 情况1：左右子树都有叶节点，计算跨当前节点的距离
        if (left.MinDepth != int.MaxValue && right.MinDepth != int.MaxValue)
        {
            currentMinDistance = left.MinDepth + right.MinDepth + 2;
        }

        // 情况2：取左右子树内部的最小距离
        currentMinDistance = Math.Min(currentMinDistance, Math.Min(left.MinDistance, right.MinDistance));

        return (currentMinDepth, currentMinDistance);
    }

    // 对外暴露的方法，返回最近叶节点间的最小距离
    public int FindMinLeafDistance()
    {
        if (Root == null)
            return 0;
        var result = CalculateMinDistance(Root);
        return result.MinDistance == int.MaxValue ? 0 : result.MinDistance;
    }
}

原代码的其他问题说明 #

1. 原代码中additionsCount的逻辑完全不符合需求，它只是记录了更新最大路径和的次数，并非叶节点间的距离。
2. Convert.ToInt32(root.Data)存在类型风险，如果Data不是数值类型会报错，建议泛型树处理数值逻辑时增加约束，比如where T : IConvertible。

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