算法——判断一棵二叉树是否是平衡二叉树

计算一棵树的高度

int height(TreeNode*p) { if(p==nullptr) return 0; return max(height(p->left),height(p->right))+1; }

真正确定上下界的检查函数

bool For_use(TreeNode*p,long long int low,long long int top) { if(p==nullptr) return true; //检查数值 if(p->val<=low) { return false; } if(p->val>=top) { return false; } //检查平衡因子 if(abs(height(p->left)-height(p->right))>1) { return false; } return For_use(p->left,low,p->val)&&For_use(p->right,p->val,top); }

调用的接口函数

bool Check_the_tree_is_banlanced_or_not(TreeNode*p) { if(p==nullptr) return true; return For_use(p,INT_MIN,INT_MAX); }

整体代码

#include<iostream> #include<vector> #include<climits> #include<cstdbool> #include<algorithm> using namespace std; typedef struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} } TreeNode; int height(TreeNode*p) { if(p==nullptr) return 0; return max(height(p->left),height(p->right))+1; } bool For_use(TreeNode*p,long long int low,long long int top) { if(p==nullptr) return true; //检查数值 if(p->val<=low) { return false; } if(p->val>=top) { return false; } //检查平衡因子 if(abs(height(p->left)-height(p->right))>1) { return false; } return For_use(p->left,low,p->val)&&For_use(p->right,p->val,top); } bool Check_the_tree_is_banlanced_or_not(TreeNode*p) { if(p==nullptr) return true; return For_use(p,INT_MIN,INT_MAX); } TreeNode*create(TreeNode*op) { int Ai; cin>>Ai; if(Ai<0) { op=nullptr; } else { op=new TreeNode(Ai); op->left=create(op->left); op->right=create(op->right); } return op; } void DFS(TreeNode*op) { if(op==nullptr) return; cout<<op->val; DFS(op->left); DFS(op->right); } int main() { TreeNode*o=nullptr; o=create(o); cout<<"树的高度："<<height(o)<<endl; cout<<"判断树是否为平衡二叉树（0为假，1为真）"<<Check_the_tree_is_banlanced_or_not(o); cout<<endl<<"前序遍历二叉树："; DFS(o); return 0; }

运行截图：