题解 | #平衡二叉树#

思路： 判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。 则可以相当将问题不断分成子问题，使用递归。

方法一：递归判断+递归计算深度 具体做法：写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函数则递归计算该结点深度。 图中为判断函数的递归图，其中计算深度函数递归也是如此。

class Solution {
public:
    int deep(TreeNode* root){//计算该子树深度
        if(root == NULL) //空结点深度为0
            return 0;
        int left = deep(root->left); //递归算左右子树的深度
        int right = deep(root->right);
        return (left > right) ? left + 1 : right + 1; //子树最大深度加上自己
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == NULL) //空树为平衡二叉树
            return true;
        int left = deep(pRoot->left);
        int right = deep(pRoot->right);
        if(left - right > 1 || left - right < -1){ //左子树深度减去右子树相差绝对值大于1
            return false;
        }
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);//同时，左右子树还必须是平衡的
    }
};

复杂度分析：

• 时间复杂度：O(n^2)， 两个递归
• 空间复杂度：O(n)，递归栈最大深度

方法二：边计算深度边判断 上述一个函数算深度，一个函数遍历所有结点的方法，用了两个递归，做了很多不必要的运算，事实上我们可以利用函数的引用，将计算的深度变量跟着递归一起走，由此一次遍历就可以算出深度又同时判断了是否为平衡二叉树。如图的从下往上边计算边判断的递归：

class Solution {
public:
    bool judge(TreeNode* root, int& depth){//计算该子树深度
        if(root == NULL){ //空结点深度为0
            depth = 0;
            return true;
        }
        int left = 0; //准备计算左右子树的深度
        int right = 0;
        if(judge(root->left, left) == false || judge(root->right, right) == false)
            return false;
        if(left - right > 1 || left - right < -1){ //左子树深度减去右子树相差绝对值大于1
            return false;
        }
        depth = (left > right) ? left + 1 : right + 1; //子树最大深度加上自己
        return true; //该结点满足要求
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return judge(pRoot, depth);
    }
};

复杂度分析：

• 时间复杂度：O(n)，一次递归
• 空间复杂度：O(n)，递归栈的深度