我的代码有什么问题检查是否平衡高度

Question

任何人都可以修复我的代码吗

  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,null,null,15,7] 输出：假 异常输出：true

案例2 输入：根 = [1,2,2,3,3,null,null,4,4] 输出：假 异常输出 = false

案例3 输入：根=[] 输出：真 异常输出=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
    }
}