剑指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)。递归栈的深度随树高h增长，辅助空间复杂度为O(h)，最坏为O(n)。

以上，本题结束！