剑指offer-平衡二叉树

本文为剑指 offer 系列第三十八篇。
主要知识点为平衡二叉树,也就是判断一棵树的左右子树的高度差是否大于1。

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

我们上一篇写过一个方法用来求一棵树的深度，
那么本题目就可以利用上面的那个方法来进行计算左右子树的深度，然后判断其高度差是否大于1。
如果大于1，则返回false,否则继续判断其子树是否为平衡二叉树。

解题代码

class Solution {
public:
    int Depth(TreeNode* root){
        if(!root) return 0;
        else return max(Depth(root->left),Depth(root->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        if(!root) return true;
        if(abs(Depth(root->left)-Depth(root->right))>1){
            return false;
        }else {
            return IsBalanced_Solution(root->left)&&IsBalanced_Solution(root->right);
        }
    }
};

时间复杂度为O(n^2),空间复杂度为O(n^2)

以上，本题结束！