解法一：自顶向下

一棵二叉树为「平衡二叉树」的条件为：该树为空树，或者其左右子树的高度差最大为1。因此，判断一棵二叉树是否平衡需要求其子树高度，并比较左右子树高度差。

因此此题的解题步骤如下：

  1. 设计「求二叉树高度」的函数getHeight(root)，作用是求以root为根结点的二叉树高度；
  2. 遍历原二叉树，对其每个结点调用getHeight(root)函数，若存在某左右子树的高度差大于等于2，则是不平衡的；否则是平衡二叉树。

求取二叉树高度的思路如图所示。

图片说明

图中，红色箭头方向为递归方向，绿色箭头方向为回溯方向。

  1. 当结点为空时，其高度为0；
  2. 当结点无左孩子、右孩子时，其高度为1；
  3. 否则，该结点的高度为max(左子树高度，右子树高度) + 1。（加1是因为要加上该结点本身）

实现的代码如下：

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* root) {
        if (!root) 
            return true;
        // 分别求左子树和右子树高度
        int leftHeight = getHeight(root->left), rightHeight = getHeight(root->right);
        // 若子树高度之差大于1，返回false
        if (abs(leftHeight - rightHeight) > 1) 
            return false;
        // 递归地判断左右子树是否平衡
        return IsBalanced_Solution(root->left) && IsBalanced_Solution(root->right);
    }
    // 求子树高度
    int getHeight(TreeNode* root) {
        if (!root) 
            return 0;
        if (!root->left && !root->right) 
            return 1; // 叶子结点
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
};

在计算一个结点的高度时，平均情况下时间复杂度为O(logN)；且对于每个结点分别计算其高度，故总时间复杂度为O(NlogN)；该算法需要递归地遍历每个结点，因此空间复杂度为O(N)。

解法二：自底向上

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

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

  1. 从最底的叶子结点开始，计算该结点的高度。若该结点不平衡，则直接返回-1，不用继续计算其他结点高度，否则返回其高度；
  2. 若自底向上的过程中一直都是平衡的，则最终的树是平衡的。

此方法每个结点（最坏时）仅会遍历一次，不会有重复计算。
图片说明

实现的代码如下：

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); // 返回该结点高度
    }
};

该方法（最坏情况）访问每个结点一次，因此时间复杂度为O(N)，该方法需要递归遍历每个结点，需要函数调用的开销，空间复杂度为O(N)。