检查给定的二叉树是否像C ++中的红黑树一样高度平衡

概念

对于一棵红黑树，一个节点的最大高度最多是最小高度的两倍。对于给定的二叉搜索树，我们需要验证以下属性。

对于每个节点，最长的叶到节点路径的长度不超过从节点到叶的最短路径上的节点的两倍。

例子

13    41
\    / \
15  11 101
\   /    \
17 61 151

上面的树不能是红黑树上面的树可以是任何颜色分配的红黑树

13的最大高度是1

最小高度13是3

   11
  / \
 6   101
 /    \
51    151
/
41

树上也可以是红黑树

在这种情况下，预期的时间复杂度为O(n)。在解决方案中，该树最多应被访问一次。

方法

对于每个节点，我们要求获取最大和最小高度并进行比较。概念是访问树，并为每个节点验证树是否平衡。我们需要编写一个递归函数，该函数返回三件事：一个布尔值（表示树是否平衡），最小高度和最大高度。要返回多个值，我们可以应用结构或通过引用传递变量。执行maxh和minhby引用传递，以便可以在父调用中应用这些值。

示例

/* This program to check whether a given Binary Tree is balanced like a Red-Black Tree or not */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
   int key;
   Node1 *left, *right;
};
Node1* newNode(int key){
   Node1* node1 = new Node1;
   node1->key = key;
   node1->left = node1->right = NULL;
   return (node1);
}
bool isBalancedUtil(Node1 *root, int &maxh1, int &minh1){
   if (root == NULL){
      maxh1 = minh1 = 0;
      return true;
   }
   int lmxh1, lmnh1;
   int rmxh1, rmnh1;
   if (isBalancedUtil(root->left, lmxh1, lmnh1) == false)
      return false;
   if (isBalancedUtil(root->right, rmxh1, rmnh1) == false)
      return false;
   maxh1 = max(lmxh1, rmxh1) + 1;
   minh1 = min(lmnh1, rmnh1) + 1;
   if (maxh1 <= 2*minh1)
      return true;
   return false;
}
bool isBalanced(Node1 *root){
   int maxh1, minh1;
   return isBalancedUtil(root, maxh1, minh1);
}
/* Driver program to test above functions*/
int main(){
   Node1 * root = newNode(11);
   root->left = newNode(6);
   root->right = newNode(101);
   root->right->left = newNode(51);
   root->right->right = newNode(151);
   root->right->left->left = newNode(41);
   isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";
   return 0;
}

输出结果

Balanced