题解 | #判断是不是平衡二叉树#

方法：递归（自顶向下）

经过每个结点都得到它的左子树和右子树的最大深度，判断每个结点的左右子树深度差是否大于1。深度差不大于1则继续递归。

时间复杂度：o(n²)。第一个递归遍历二叉树所有节点，第二个递归查找深度最坏情况下（二叉树退化为链表）需要遍历二叉树所有节点。

空间复杂度：o(n)

class Solution {
  public:
    //获取树的最大深度
    int getDepth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        return max(getDepth(root->left) + 1, getDepth(root->right) + 1);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr)
            return true;

        int left_depth = getDepth(pRoot->left);
        int right_depth = getDepth(pRoot->right);
        //一旦发现左子树与右子树的深度差大于1，直接返回false;
        if ((left_depth - right_depth) > 1 || (left_depth - right_depth) < -1)
            return false;

        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

方法：递归（自底向上）

可以自底向上，从数的底部开始一边计算左右子树的深度，一边计算结点的左右子树是否为平衡二叉树，这样可以节省时间复杂度。

时间复杂度：o(n)。

空间复杂度：o(n)

class Solution {
  public:
    bool judgeBalance(TreeNode* root, int& depth) {
        if (root == nullptr)
            return true;

        int left_depth = 0;
        int right_depth = 0;
        if (judgeBalance(root->left, left_depth) == false ||
            judgeBalance(root->right, right_depth) == false)
            return false;

        if (left_depth - right_depth > 1 || right_depth - left_depth > 1)
            return false;
		//得到最大深度
        depth = (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;

        return true;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return judgeBalance(pRoot, depth);
    }
};