Judge whether a binary tree is a balanced binary tree

1、 subject

Given a binary tree , Judge whether this binary tree is a balanced binary tree .

2、 Ideas

Use the recursive routine of binary tree to solve this problem .

If the X A tree with nodes as roots is a balanced binary tree , Then three conditions must be met ：

1. The left subtree is balanced
2. The right subtree is balanced
3. The absolute value of the height difference between the left and right subtrees is less than 2

that X The information that the node needs to get from the left tree ：① Is it balanced ;② Height

Empathy ,X The node needs the information obtained from the right tree ：① Is it balanced ;② Height

such , We can know whether the tree is balanced .

therefore , Use structure Info Save these two information , Every node is treated equally , Such treatment is required .

3、 Realization

/************************************************************************* > File Name: 034. Determine whether a binary tree is a balanced binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  5、 ... and  7/ 1 15:07:04 2022 ************************************************************************/

#include <iostream>
#include <ctime>
using namespace std;

class TreeNode {
    
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {
    }
};

// Method 1 ： recursive 
int getHeight(TreeNode *root) {
    
    if (root == nullptr) return 0;

    return max(getHeight(root->left), getHeight(root->right)) + 1;
}

bool isBalanced1(TreeNode *root) {
    
    if (root == nullptr) return true;
    return isBalanced1(root->left) 
            && isBalanced1(root->right) 
            && abs(getHeight(root->left) - getHeight(root->right)) < 2;
}

// Method 2 :  Binary tree recursive routine solution 
class Info {
    
public:
    bool isBalanced; // Is it balanced 
    int height; // Height 

    Info(bool isB, int h) : isBalanced(isB), height(h) {
    }
};

Info *process(TreeNode *x) {
    
    if (x == nullptr) {
    
        return new Info(true, 0);
    }

    Info *leftInfo = process(x->left);
    Info *rightInfo = process(x->right);

    bool isBalanced = leftInfo->isBalanced && rightInfo->isBalanced && abs(leftInfo->height - rightInfo->height) < 2;
    int height = max(leftInfo->height, rightInfo->height) + 1;

    return new Info(isBalanced, height);
}

bool isBalanced2(TreeNode *root) {
    
    return process(root)->isBalanced;
}


//for test 
TreeNode *generate(int level, int maxLevel, int maxVal) {
    
    if (level > maxLevel || (rand() % 100 /(double)101)  < 0.5) 
        return nullptr;

    TreeNode *root = new TreeNode(rand() % maxVal);
    root->left = generate(level + 1, maxLevel, maxVal);
    root->right = generate(level + 1, maxLevel, maxVal);
    return root;
}


TreeNode *generateRandomBST(int maxLevel, int maxVal) {
    
    return generate(1, maxLevel, maxVal);
}

int main() {
    
    srand(time(0));
    int maxLevel = 5;
    int maxVal = 100;
    int testTime = 1000001;

    for (int i = 0; i < testTime; i++) {
    
        TreeNode *root = generateRandomBST(maxLevel, maxVal);
        //cout << "isBalanced1(root) = " << isBalanced1(root) << endl;
        //cout << "isBalanced2(root) = " << isBalanced2(root) << endl;
        if (isBalanced1(root) != isBalanced2(root)) {
    
            cout << "Oops!" << endl;
            break;
        }
    }
    cout << "finish!" << endl;
    return 0;
}