有一棵二叉树，请设计一个算法判断这棵二叉树是否为平衡二叉树。
给定二叉树的根结点root，请返回一个bool值，代表这棵树是否为平衡二叉树。
思路：左子树是否为平衡二叉树，左子树最深到哪一层；右子树是否为平衡二叉树，右子树最深到哪一层；如果左右子树都是平衡二叉树，比较它们的层数差。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class CheckBalance { public: bool check(TreeNode* root) { if(root==NULL) return true; int l=getHeight(root->left); int r=getHeight(root->right); if(abs(l-r) > 1) //如果其相差大于1，则说明以当前root为头的二叉树不是 AVL return false; return check(root->left)&&check(root->right); } int getHeight(TreeNode* root){ if(root==NULL) return 0; // 如果当前 root 为空，则返回当前深度0 if(root->left==NULL && root->right==NULL) return 1; int left=getHeight(root->left);// 获得以当前 root 为头的左子树深度 int right=getHeight(root->right); // 获得以当前 root 为头的右子树深度 //获得当前左子树深度和右子树深度的最大值， return max(left,right)+1; } };
