LeetCode 110 平衡二叉树

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

1.1 DFS自顶向下暴力法实现

class Solution {
public:
    int getDepth(TreeNode *root){
        if(root){
            return max(getDepth(root->left),getDepth(root->right))+1;
        }
        return 0;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int d_l=getDepth(root->left);
        int d_r=getDepth(root->right);
        return abs(d_r-d_l)<=1&&isBalanced(root->left)&&isBalanced(root->right);
    }
};

此处存在时间复杂度的浪费，在深度计算上还存在这优化的空间。在计算深度时存在这对统一节点深度的反复计算。

1.2 DFS自底向上搜索

本质思想就是先判断子树是否是平衡二叉树，当子树是一颗平衡二叉树时，希望能够返回树的深度（如何返回二叉树的深度）。若是子树不平衡，那么整个树一定都是不平衡的。

关于深度的计算：当前节点为空时，直接返回0值，当前节点非空，则需要判断，需要理解递归的思想，在当前节点的两颗子树都是平衡二叉树时，只需要返回max深度+1即可。

class Solution {
public:
    int balance(TreeNode *root){  // 判断子树是否平衡的同时返回深度值，实际上就是获取到深度后再判断，-1表示不平衡
        if(root){
            int bl=balance(root->left);
            int br=balance(root->right);
            return (bl!=-1&&br!=-1&&abs(bl-br)<=1)?max(br,bl)+1:-1;
        }else{
            return 0;
        }
    }
    bool isBalanced(TreeNode* root) {  // 在总体的函数中就只需要进行简单的判断
        if(!root) return true;
        int bl=balance(root->left);
        int br=balance(root->right);
        return (bl!=-1&&br!=-1&&abs(bl-br)<=1);
    }
};