首页 > 代码库 > careercup-树与图 4.1

careercup-树与图 4.1

4.1 实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个结点,其两颗子树的高度差不超过1.

 

C++实现代码:

#include<iostream>#include<new>#include<cmath>using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};void createTree(TreeNode *&root){    int i;    cin>>i;    if(i!=0)    {        TreeNode *tmp=new TreeNode(i);        root=tmp;        createTree(root->left);        createTree(root->right);    }}int high(TreeNode *root){    if(root==NULL)        return 0;    if(root->left==NULL&&root->right)        return 1;    int lhigh=high(root->left);    int rhigh=high(root->right);    return (lhigh>=rhigh)?lhigh+1:rhigh+1;}bool isAVL(TreeNode *root){    if(root==NULL)        return true;    if(root->left==NULL&&root->right==NULL)        return true;    int lhigh=high(root->left);    int rhigh=high(root->right);    if(abs(lhigh-rhigh)<2)        return isAVL(root->left)&&isAVL(root->right);    return false;}int main(){    TreeNode *root=NULL;    createTree(root);    cout<<high(root)<<endl;    cout<<isAVL(root)<<endl;}

 

careercup-树与图 4.1