//方法一：使用深度遍历,判断每个节点是不是平衡二叉树，这种从上至下的方法会导致底层的节点重复判断多次

 class Solution01 {

 public:

     bool IsBalanced_Solution(TreeNode* pRoot) {

         if (pRoot == nullptr)return true;

         int left = getHeight(pRoot->left);

         int right = getHeight(pRoot->right);

         if (abs(left - right) > )return false;

         return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

     }

 private:

     int getHeight(TreeNode *pRoot)

     {

         if (pRoot == nullptr)return ;

         int left = getHeight(pRoot->left);

         int right = getHeight(pRoot->right);

         return max(left, right) + ;

     }

 };

 //方法二：使用后序遍历判断，这种方法为自下而上，每个节点只需要判断一次即可

 class Solution02 {

 public:

     bool IsBalanced_Solution(TreeNode* pRoot) {

         if (pRoot == nullptr)return true;

         int level = ;

         return IsBalanced_Solution(pRoot, level);

     }

 private:

     bool IsBalanced_Solution(TreeNode* pRoot, int &level)

     {

         if (pRoot == nullptr)

         {

             level = ;

             return true;

         }

         //按照后序遍历去判断左右子树，然后以当前节点为根树的深度

         int left = , right = ;

         if (IsBalanced_Solution(pRoot->left, left) && IsBalanced_Solution(pRoot->right, right))

         {

             if (abs(left - right) <= )

             {

                 level = max(left, right) + ;

                 return true;

             }

         }

         return false;

     }

 };