leetcode 110。平衡二叉树，平衡树代码的问题

Question

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

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

对于这个问题，高度平衡的二叉树定义为：

一种二叉树，其中每个节点的左右子树的高度相差不超过1。

我已经看到了这个问题的解决方案，包括这个：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b){
    return (a > b) ? a:b;
}
int height(struct TreeNode* root){
    if(root == NULL) return 0;
    return 1 + max(height(root->left),height(root->right));
}
bool isBalanced(struct TreeNode* root){
    if(root == NULL) return 1;
    int left = height(root->left);
    int right = height(root->right);
    
    return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

我的问题是：为什么要添加此代码？

isBalanced(root->left) && isBalanced(root->right);

当我从代码中删除它时，它看起来工作得很好。但是，当测试用例为< code>[1，2，2，3，null，null，3，4，null，null，4]时，代码将返回true，而预期答案为false。

我对这个测试充满了疑问，因为测试树的两端都是一样的深度，所以abs（左右）应该是0，而0

Answer 1

一种二叉树，其中每个节点的左右子树的高度相差不超过1。

在这里，您已经提到了为什么您的实现会引发错误。您的代码仅检查根节点（最顶层节点）的高度平衡。

平衡树中每个节点的高度差一定是[-1，0，1]。更简单的可视化是考虑每个节点本身有一棵小树。

假设这是测试用例< code>[1，2，2，3，null，null，3，4，null，null，4]。

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

如果只检查根节点，则< code>abs(left-right)为0。但是考虑左边的节点2。把它想象成一棵更小的树或子树。

     2  
    /    
   3      
  /         
 4        

如果这是一棵树本身，那么它就不平衡，因为abs（左-右）== 2。由于我们发现了一个不平衡的节点，因此返回 false。

因此，为了解决这个问题，我们必须将每个节点视为一个单独的树本身。此类问题需要递归算法，通过递归调用它们的子节点，从最高节点到最低节点检查isBal的属性。

Answer 2

测试用例是< code>[1，2，2，3，null，null，3，4，null，null，4]，

因此，让我们可视化该树：

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

代码将返回 true，而预期的答案是假的，

预期的答案是false：上面的树不是平衡树。

我对这个测试充满了疑问，因为测试树的两端都是一样的深度，所以abs（左右）应该是0，而0

您说得对，abs(left-right)是0，并且在界限[-1，1]内，但是在平衡树中，这个条件在每个节点中都必须为真。因此，您的代码还必须检查< code>abs(left-right)是否在其他节点的限制范围内。然后您可以看到值为2的第一个节点有一个左子树，比它的右子树(为空)高2级。所以我们违反了规则，正确答案是< code>false。

这解释了为什么您真的需要这两个对< code>isBalanced的递归调用。