LeetCode平衡二叉树解法疑问：测试用例返回异常结果

我在LeetCode上完成了平衡二叉树基础题，解法已被系统接受，但运行时发现问题：

• 测试用例1（平衡树）返回正确结果True；
• 测试用例2（不平衡树）预期返回False，但实际返回True。

我采用递归遍历所有节点的方式实现，想排查下代码是否存在bug或逻辑错误。

我的代码： #

static bool IsBalanced(BinaryTree root) {
    isBalanced = true;

    int chk = CheckBalance(root.Root, 0);

    return isBalanced;
  }

  static int CheckBalance(TreeNode root, int depth) {
    if (root == null)
      return 0;

    int left = CheckBalance(root.left, depth + 1);
    int right = CheckBalance(root.right, depth + 1);

    if (Math.Abs(left - right) > 1)
      isBalanced = false;
    return GetMax(left, right);
  }

  static int GetMax(int left, int right) {
    if (left > right)
      return left;
    else
      return right;
  }

测试用例1： #

3
      / \
     9  20
        / \
       15  7

输出：True（正确）

测试用例2： #

1
       / \
      2   2
     / \
    3   3
   / \
  4   4

预期输出：False，实际返回：True

问题分析与修复 #

你的代码核心问题出在子树深度计算错误：CheckBalance函数返回的是左右子树深度的最大值，但没有加上当前节点的深度偏移（即+1）。这导致所有节点的子树深度计算都被低估，测试用例2中左右子树的深度差值始终无法触发Math.Abs(left - right) > 1的判断条件，最终错误返回True。

修正后的CheckBalance函数需要返回GetMax(left, right) + 1，这样才能正确累加当前节点的深度：

static int CheckBalance(TreeNode root, int depth) {
    if (root == null)
      return 0;

    int left = CheckBalance(root.left, depth + 1);
    int right = CheckBalance(root.right, depth + 1);

    if (Math.Abs(left - right) > 1)
      isBalanced = false;
    return GetMax(left, right) + 1; // 新增+1，正确计算当前子树深度
}

另外，函数参数里的depth实际上没有被使用，可以直接移除，不影响逻辑。

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