判断是不是平衡二叉树

方法一：自顶向下，依次判断根是否，左子树是否，右子树是否

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
      if(!pRoot)return true;
      int l = high(pRoot->left);
      int r = high(pRoot->right);
      if(abs(l-r) > 1)return false;//判断根
       return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);//左右子树判断
    }
    int high(TreeNode* t){
        if(!t)return 0;
        return max(high(t->left),high(t->right))+1;
    }
};

方法二：自底向上，后序遍历，回溯过程依次判断左右树是否满足，不满足为-1直接返回

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot)return true;
        return fun(pRoot) == -1 ? false : true;
    }
    int fun(TreeNode* t){
        if(!t)return 0;
        int l = fun(t->left);//左树高度
        if(l == -1)return -1;
        int r  = fun(t->right);//右树高度
        if(r == -1)return -1;
        if(abs(l-r) > 1)return -1;
        return max(r,l) + 1;
    }
};