检查二叉树是否平衡时输出错误

Question

我正在尝试解决LeetCode问题110。平衡二叉树:

给定一棵二叉树，确定它是否是高度平衡。

这是我的尝试：

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);
    }
}

我得到以下输入的错误结果：

          3
         / \
        9   20
           /  \
         15    7

按级别顺序编码：

[3,9,20,null,null,15,7]

预期输出为 true，但我的代码返回 false。

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
    }

我的错误是什么？

Answer 1

您的代码的问题在于，您有时期望

helper

返回高度，有时期望返回高度的 difference。例如：

• 在

  isBalanced

  中，您期望

  helper(root,0)

  返回差异
• 在

  helper

  中，您期望

  helper(root.left,count+1)

  和

  helper(root.right,count+1)

  返回高度。
• 在

  helper

  中，所有

  return

  语句都返回高度，而不是高度差。

您需要明确区分两者。由于您的身高都是无符号整数，因此您可以保留值 -1 来指示发现不平衡，如果是这样，则将这个 -1 一直向上冒泡到

helper

的初始调用，以便

isBalanced

通过将返回值与-1进行比较就可以知道整棵树是否平衡。

不是问题，但你的条件

diff < 0

永远不会成立，因为

diff

是一个绝对值。

这里是用这个想法对你的代码进行的更正：

class Solution {
    public boolean isBalanced(TreeNode root) {
        int result = helper(root, 0); // returns a height, or -1 if not balanced
        return result != -1;
    }

    int helper(TreeNode root,int count){
        if (root==null) {
            return count;
        }
        int a=helper(root.left,count+1);
        if (a == -1) return -1; // Don't bother continuing: we already know the tree is not balanced!
        int b=helper(root.right,count+1);
        if (b == -1) return -1; // ..idem..
        int diff=Math.abs(a-b);
        if (diff > 1) // Not balanced!
            return -1;  // Special value to indicate the tree is not balanced
        return Math.max(a, b); // The height of a balanced tree
    }
}