原题

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

判断一棵树是否是平衡二叉树，

注意的问题

　　　　　　1）：递归判断左右子树的平衡性(第12行)

　　　　　　2）：左右子树高度相差大于1，而不是等于2，这不是生成平衡树(第10行)

　　　　　　3）：平衡树是不是搜索树？这是一个问题。。。

1  class Solution  2   { 3   public: 4       bool isBalanced(TreeNode* root)  5           { 6               if (root == NULL) 7                   return true; 8                int lh = height(root->left); 9               int rh = height(root->right);10              if(lh - rh > 1 || rh - lh > 1)11                  return false;12              return isBalanced(root->left)&&isBalanced(root->right);13          }14  //求节点高度15      int height(TreeNode* &pos)16      {17          if(pos == NULL)18              return -1;19        //返回节点高度20          return max(height(pos->left),height(pos->right)) + 1; 21      }22  };

1 class Solution  2  { 3  public: 4      bool isBalanced(TreeNode* root)  5      { 6          if (root == NULL) 7              return true; 8          bool IsSearch = true; 9          int lh = height(root->left,IsSearch);10          int rh = height(root->right,IsSearch);11          if(lh - rh == 2 || rh - lh == 2 || !IsSearch)12              return false;13          return true;14      }15      //求节点高度16      int height(TreeNode* &pos,bool &charge)17      {18          if(pos == NULL)19              return -1;20          if (pos->right != NULL)21          {22              if(pos->val >= pos->right->val)23              {24                  charge = false;25                  return 0;26              }27          }28          else if(pos->left != NULL)29          {30              if(pos->val <= pos->left->val)31              {32                  charge = false;33                  return 0;34              }35          }36          if(charge)37              return max(height(pos->left,charge),height(pos->right,charge)) + 1; 38          else39              return 0;40      }41  };