Balanced Binary Tree

这个麻烦在，对以一个结点为根的树，左右树都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;    }};