如何将一般树平衡判断的指数时间C#代码优化为线性时间？

你的问题我太懂了——原代码里isBalanced和height分开递归调用，导致同一个子树被反复遍历计算，时间复杂度直接飙到指数级，完全没必要。

核心解决思路就是把「计算子树高度」和「判断子树平衡」合并到一次遍历里。我们可以写一个辅助函数，每次递归时同时返回两个关键信息：当前子树是否平衡，以及当前子树的高度。这样每个节点只会被访问一次，时间复杂度直接降到O(n)，空间上也只是递归栈的开销（或者迭代实现的话用队列/栈），完全符合你的要求。

优化后的C#代码 #

using System;

namespace BalancedTree
{
    public class MainClass
    {
        // 外部调用的入口函数
        static bool IsBalanced(int[][] sons)
        {
            // 调用辅助函数，只关心平衡结果
            return IsBalancedAndGetHeight(sons, 0).IsBalanced;
        }

        // 辅助函数：同时返回当前子树的平衡状态和高度
        static (bool IsBalanced, int Height) IsBalancedAndGetHeight(int[][] sons, int startNode)
        {
            // 叶子节点：平衡，高度为1
            if (sons[startNode].Length == 0)
            {
                return (true, 1);
            }

            bool isSubtreeBalanced = true;
            int maxChildHeight = 0;
            int minChildHeight = int.MaxValue;

            foreach (int childNode in sons[startNode])
            {
                // 递归获取子节点的平衡状态和高度
                var childResult = IsBalancedAndGetHeight(sons, childNode);

                // 如果子树已经不平衡，直接标记当前树不平衡
                if (!childResult.IsBalanced)
                {
                    isSubtreeBalanced = false;
                    // 可选：提前终止循环，减少不必要的遍历
                    // break;
                }

                // 更新子树的最大和最小高度
                if (childResult.Height > maxChildHeight)
                {
                    maxChildHeight = childResult.Height;
                }
                if (childResult.Height < minChildHeight)
                {
                    minChildHeight = childResult.Height;
                }
            }

            // 注意：你的平衡定义是「根到所有叶子路径长度相同」，因此所有子树高度必须严格相等
            // 原代码的高度差<2不符合这个定义，这里修正为严格相等判断
            bool currentBalanced = isSubtreeBalanced && (maxChildHeight == minChildHeight);
            // 当前树的高度是子树高度+1
            int currentHeight = maxChildHeight + 1;

            return (currentBalanced, currentHeight);
        }

        public static void Main(string[] args)
        {
            int[][] sons = new int[6][];
            sons[0] = new int[] { 1, 2, 4 };
            sons[1] = new int[] { };
            sons[2] = new int[] { 3, 5 };
            sons[3] = new int[] { };
            sons[4] = new int[] { };
            sons[5] = new int[] { };
            Console.WriteLine(IsBalanced(sons)); // 输出false：节点0的子树高度不一致
        }
    }
}

关键细节说明 #

• 合并遍历逻辑：辅助函数IsBalancedAndGetHeight在一次递归中完成子树平衡判断和高度计算，每个节点仅被访问一次，彻底消除重复计算，时间复杂度降至O(n)。
• 修正平衡判断逻辑：你定义的平衡是「所有叶子路径长度相同」，这要求所有子树的高度必须严格相等，原代码的高度差<2不符合这个要求，这里做了修正。
• 提前终止优化（可选）：如果遍历子节点时发现某棵子树已经不平衡，可以直接中断循环，减少不必要的递归调用，进一步提升性能。
• 元组返回值：用C#的ValueTuple同时返回两个结果，代码简洁易读；如果是旧版本C#，可以用自定义类或out参数实现同样效果。

复杂度分析 #

• 时间复杂度：O(n)，每个节点仅被遍历一次，总操作数与节点数线性相关。
• 空间复杂度：O(h)，h为树的高度，对应递归栈的深度。如果树是链状结构，h=n；如果是平衡树，h=logn。若担心递归栈溢出，可改为迭代式深度优先/广度优先遍历，空间复杂度仍为O(n)。

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