验证平衡二叉树时输出错误，请求排查代码问题

我正在解决LeetCode第110题「Balanced Binary Tree」，题目要求判断给定二叉树是否为高度平衡（height-balanced）。当测试以下二叉树时，预期输出true，但我的代码返回false，请帮忙排查错误。

测试用例的二叉树结构：

3
         / \
        9   20
           /  \
         15    7

其层序遍历编码为[3,9,20,null,null,15,7]

我的实现代码 #

class Solution {
    boolean c = true;

    public boolean isBalanced(TreeNode root) {
        int diff = helper(root, 0);
        System.out.println(diff);
        if ((diff > 0 && diff < 2) || root == null)
            return true;
        return false;
    }

    int helper(TreeNode root, int count) {
        if (root == null) {
            return count;
        }
        int a = helper(root.left, count + 1);
        int b = helper(root.right, count + 1);
        int diff = Math.abs(a - b);
        if (diff > 1 || diff < 0)
            return count;
        return Math.max(a, b);
    }
}

TreeNode类定义 #

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

复现问题的main代码 #

public static void main(String[] args) {
    Solution solution = new Solution();

    TreeNode tree = new TreeNode(3, 
        new TreeNode(9), 
        new TreeNode(20,
            new TreeNode(15),
            new TreeNode(7)
        )
    );
    
    boolean result = solution.isBalanced(tree);
    System.out.println("result " + result); // false, but should be true
}

代码错误分析 #

1. 核心逻辑误解：helper返回值用途错误
   你的helper函数实际返回的是树的最大高度，但isBalanced函数却把这个高度值当成了高度差来判断，这是最根本的错误。测试用例中helper返回的是根节点的高度2，不满足diff >0 && diff <2的条件，因此错误返回false。

2. helper函数的错误分支处理
   当发现左右子树高度差超过1时，你返回当前的count，这会破坏上层递归的高度计算逻辑，导致后续高度值完全失真。而且diff <0的判断毫无意义，绝对值不可能小于0。

3. 全局变量未利用
   你定义了全局变量c但完全没在逻辑中使用，属于冗余代码，原本可以用它来标记是否出现不平衡的情况。

修正后的代码示例 #

class Solution {
    boolean isBalanced = true;

    public boolean isBalanced(TreeNode root) {
        getHeight(root);
        return isBalanced;
    }

    int getHeight(TreeNode root) {
        if (root == null || !isBalanced) { // 提前终止递归，优化性能
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        // 检查当前节点的左右子树高度差
        if (Math.abs(leftHeight - rightHeight) > 1) {
            isBalanced = false;
        }
        // 返回当前节点的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

修正点说明 #

• 用全局变量isBalanced标记树是否平衡，一旦发现高度差超过1就设为false，后续递归可提前终止
• getHeight函数正确计算树的高度，同时在计算过程中检查平衡条件
• isBalanced函数直接返回全局变量的状态，逻辑清晰直观

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