推断的思路非常easy。若一棵树是平衡二叉树，它的左右子树都是平衡二叉树，而且左右子树的高度差小于等于1。注意。实现的时候，推断左右子树的平衡性时。能够顺便计算子树高度，不用再另外计算一次。以下是其递归实现：

#include 
     
      using namespace std;struct TreeNode {	int val;	TreeNode *left;	TreeNode *right;	TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    bool isBalanced(TreeNode *root) {        int height;		return myBalance(root,height);    }	bool myBalance(TreeNode *root, int &height){//注意，将height用引用传进来		if(root==NULL){//若为空，高度就为0，平衡			height=0;			return true;		}		int leftHeight;		int rightHeight;		bool leftBalance=myBalance(root->left,leftHeight);//root的左子树平衡吗？		bool rightBalance=myBalance(root->right,rightHeight);//root的右子树平衡吗？		height=max(leftHeight,rightHeight)+1;//以root为根的这棵树的高度。是root的左子树、右子树中的较高者加上root本身这个结点（即加1）		if(leftBalance && rightBalance && abs(leftHeight-rightHeight)<=1)//假设左子树平衡，右子树平衡，而且左右子树高度差小于等于1			return true;		return false;	}};int main(){	TreeNode *root=new TreeNode(1);	TreeNode *left=new TreeNode(2);	TreeNode *right=new TreeNode(3);	root->left=left;	root->right=right;	Solution *s=new Solution();	cout<
      
       isBalanced(root)<