题目描述：

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树.

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 样例解释：

样例二叉树如图，为一颗平衡二叉树 注：我们约定空树是平衡二叉树。

数据范围：100n≤100,树上节点的val值满足 10000≤n≤1000
要求：空间复杂度O(1)，时间复杂度 O(n)

题解1：求二叉树深度，自顶向下求

1. 先求从根节点开始的左子树的深度和右子树的深度
2. 如果深度差的绝对值大于1，说明不是平衡二叉树
3. 如果深度差的绝对值小于等于1，还不一定是平衡二叉树，还要对左子树的左右子树进行判断以及对右子树的左右子树进行判断。

图示来自牛客786963925号

代码

class Solution {
public:
  //二叉树的深度
    int treeDepth(TreeNode * root){
        if(!root) return 0;
        int l = treeDepth(root->left);
        int r = treeDepth(root->right);
        return max(l,r)+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot) return true;
        //先求从根节点开始的左子树的深度
        int left = treeDepth(pRoot->left);
        //再求从根节点开始的右子树的深度
        int right = treeDepth(pRoot->right);
        if(abs(left-right) >1)
            return false;
        //分别求左右子树的左右子树的深度，看是否满足平衡二叉树的要求
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

题解2：求二叉树深度，自下向上求。该题解来自牛客786963925号，再次引用其图示和代码

解法一在「计算二叉树高度」时遍历了树的结点，在「判断是否平衡」时又遍历了一次树的结点，因此产生了重复计算。

针对解法一的优化是采用「自底向上」的解题思路：

从最底的叶子结点开始，计算该结点的高度。若该结点不平衡，则直接返回-1，不用继续计算其他结点高度，否则返回其高度； 若自底向上的过程中一直都是平衡的，则最终的树是平衡的。 此方法每个结点（最坏时）仅会遍历一次，不会有重复计算。

图示

代码

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (!pRoot) 
            return true; 
        return getHeight(pRoot) >= 0; // 若结果不是-1，则是平衡的
    }
    int getHeight(TreeNode* root) {
        if (!root) 
            return 0; 
        // 左子树高度
        int left = getHeight(root->left); 
        if (left == -1) 
            return -1; // 若左子树高度为-1，则不平衡
        int right = getHeight(root->right); // 右子树高度
        if (right == -1 || abs(left - right) >= 2) 
            return -1; // 若右子树高度为-1，或左右子树高度之差大于1，则不平衡
        return 1 + max(left, right); // 返回该结点高度
    }
};