检查二叉树是否平衡

Question

我实现了下面这段C++代码，用于检测二叉树是否平衡，即左右子树高度差不超过1。然而，我不确定它是否高效，或者在检查子树时有没有问题。请问有人能给我指导吗？

 unordered_map <Node*, int>  height;
    struct Node{
       int key;
       Node* left;
       Node* right;
    }
    bool isBalanced(Node* root){
        if (root == nullptr){
             height[root] = -1;
            return true;
        }
        if (!isBalanced(root->left)) return false;
        if (!isBalanced(root->right)) return false;

        height[root] = max(height[root->left], height[root->right]) + 1;


        return (abs(height[root->left] - height[root->right]) < 1);
}

- user25004

---

你可以使 isBalanced 函数返回一个整数类型 int，返回值为 -1 表示不平衡，否则返回深度。这样你就无需额外使用字典结构。 - Slava

有很多平衡树，具体指什么是平衡的。无论如何，您应该返回高度并比较左右子树的高度。 - Jean-Baptiste Yunès

@DieterLücking 混淆。您的意思是什么？ - user25004

@DieterLücking 你的意思是有一个bug吗？ - user25004

如果您确定您的代码确实有效，并且正在寻求改进，请在SE Code Review上提问，并提供完整的代码。 - πάντα ῥεῖ

Answer 1

我会尝试使用伪代码来表达这个想法。

int CheckTreeHeight(Node root)
{
  if(root == null) return 0; // Height of 0.

  // Check if left is balanaced
  int leftChildHeight = CheckTreeHeight(root.left);
  if(leftChildHeight == -1) return -1; // Not Balanced

  // Check if right is balanaced
  int rightChildHeight = CheckTreeHeight(root.right);
  if(rightChildHeight == -1) return -1; // Not Balanced

  // Check if current node is balanced
  int heightDifference = leftChildHeight - rightChildHeight;

  if(Math.abs(heightDifference) > 1)
   return -1; // not balanaced
  else
   return Math.max(leftChildHeight, rightChildHeight) + 1; // Return Height
}

bool IsBalanced(Node root)
{
   if(CheckTreeHeight(root) == -1)
   {
      return false;
   }
   else
   {
      return true;
   }
}

这个算法的时间复杂度为O(n)，空间复杂度为O(H)，其中H是树的高度。

正如算法作者所述，我们递归地检查根节点的子节点（即left和right），直到找到不平衡的子树，返回-1。

通过这种技巧，如果任何一个子树不平衡，我们就立即返回。

有关此实现的更多信息，请参见下面引用的书籍。 参考资料
Cracking the Coding Interview第6版

- Rafael

---

如果(条件)返回false；否则返回true；看起来很丑，应该使用return !condition代替。 - Slava