這個麻煩在，對以一個結點為根的樹，左右樹都Balance，左右樹的差小于1同時滿足才行。第一種，每一個算Balance都要算到下面的height，然后復雜度O（N^2）

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool isBalanced(TreeNode* root) {         if(root==NULL) return true;         if(root->left==NULL)         {             if(height(root->right)>0)                return false;                            return true;                       }                  if(root->right==NULL)         {             if(height(root->left)>0)                return false;                             return true;                    }                           if(isBalanced(root->left)&&isBalanced(root->right)&&(abs(height(root->left)-height(root->right))<=1))         {             return true;         }                          return false;    }        int height(TreeNode * root)    {        if(root==NULL)            return -1;                 int a=height(root->left);        int b=height(root->right);        return (a>b)?(a+1):(b+1);    }        };
第二種，基于DFS，這種用一個-1做標識，最后不是-1的就是banlance，過程中只要有不平衡就會標記-1。這樣復雜度是O（n）
/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool isBalanced(TreeNode* root) {        return dfsHeight(root)!=-1;    }            int dfsHeight(TreeNode * root)    {        if(root==NULL) return 0;                int leftHeight=dfsHeight(root->left);        if(leftHeight==-1) return -1;        int rightHeight=dfsHeight(root->right);        if(rightHeight==-1) return -1;                if(abs(leftHeight-rightHeight)>1)        return -1;        return max(leftHeight,rightHeight)+1;    }};