用c++写一下判断二叉树是不是二叉平衡树的算法
时间: 2023-12-19 08:04:42 浏览: 27
以下是判断二叉树是否为平衡二叉树的C++代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 判断是否为平衡二叉树
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
}
// 计算左右子树的深度
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
// 判断左右子树的深度差是否大于1,如果大于1则不是平衡二叉树
if (abs(leftDepth - rightDepth) > 1) {
return false;
}
// 递归判断左右子树是否都是平衡二叉树
return isBalanced(root->left) && isBalanced(root->right);
}
// 计算树的深度
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->left = new TreeNode(6);
if (isBalanced(root)) {
cout << "This is a balanced binary tree." << endl;
} else {
cout << "This is not a balanced binary tree." << endl;
}
return 0;
}
```
算法思路:
1. 首先计算二叉树的深度,可以使用递归的方式求解;
2. 然后分别计算左右子树的深度,判断其深度差是否大于1;
3. 如果深度差大于1,则不是平衡二叉树,直接返回false;
4. 如果深度差小于等于1,则需要继续递归判断左右子树是否都是平衡二叉树,如果都是平衡二叉树,则返回true,否则返回false。