检查二叉树是否为高度平衡树？

题：

给定二叉树的根节点，请检查该树是否为高度平衡的树。

什么是高度平衡树？

如果左右的高度差不超过1，则称为高度平衡树。

这意味着该值应介于（-1，0，1）之间。

例：

考虑下图

如果我们只有1个节点，则高度为0。

如果我们有2个节点，

根节点16处的高度为1– 1 = 0

考虑下图

1.节点16处的高度为=正确的高度– left height

右高度= 2，左高度= 2。

因此，节点16的高度为0。

2.节点10处的高度为=正确的高度– left height

右高度= 1，左高度= 1。

因此，节点10的高度为0。

这样，我们必须计算每个节点的高度。如果该值在任何节点上都大于1，则该树不是高度平衡树。

C ++解决方案

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int is_balanced(Node *node) 
{
    if (node == NULL) 
    {
      return 0;
    }
    
    if(node->left == NULL && node->right == NULL) 
    {
      return 1;
    }

    int lH = is_balanced(node->left);
    int rH = is_balanced(node->right);
    
    if(lH == -1 || rH == -1 || abs(lH - rH) > 1) 
    {
      return -1;
    }

    return max(lH, rH) + 1;
}
  

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    if (is_balanced(root))
    {
        cout<<"Binary tree is a balanced tree"<<endl;
    } else {
        cout<<"Binary tree is NOT a balanced tree"<<endl;
  
    }




    return 0;  
}  

输出：

Binary tree is a balanced tree