思路: 判断某二叉树是否为平衡二叉树,就需要判断任意一结点两边子树深度相差是否绝对值大于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),递归栈的深度