3

我在下面实现了一段 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);
}
4

1 回答 1

3

我将尝试使用伪代码来传递这个想法。

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。

使用这种技术，如果任何子树不平衡，我们会立即返回。

您可以在下面参考文献中提到的书中找到有关此实现的更多信息。

参考
破解编码面试第6版

于 2016-02-23T20:07:41.403 回答