判断一棵二叉树是否为平衡二叉树

1、题目

给定一棵二叉树，判断这棵二叉树是不是平衡二叉树。

2、思路

使用二叉树的递归套路解决这个问题。

如果以 X 节点为根的一棵树是平衡二叉树，那么必须满足三个条件：

1. 左子树是平衡的
2. 右子树是平衡的
3. 左右子树的高度差的绝对值小于 2

那么 X 节点需要向左树获取的信息：①是否平衡；②高度

同理，X 节点需要向右树获取的信息：①是否平衡；②高度

这样，就能知道这棵树是否平衡。

所以，使用结构体 Info 保存这两个信息，每个节点一视同仁，都要进行这样的处理。

3、实现

/************************************************************************* > File Name: 034.判断二叉树是否为平衡二叉树.cpp > Author: Maureen > Mail: [email protected] > Created Time: 五 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) {
    }
};

//方法一：递归
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;
}

//方法二: 二叉树递归套路求解
class Info {
    
public:
    bool isBalanced; //是否平衡
    int 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;
}