描述

题目描述

给定我们一个二叉树, 然后让我们去判断这个是不是一个平衡二叉树, 这里我们给的定义是什么呢?

这里我们给出的定义就是二叉树的每一个节点的左右子树的高度差绝对值不超过$11$, 并且他的左右子树都是满足条件的, 那么我们称之为是平衡二叉树

那么我们可以有两个方法, 第一种就是从上而下的递归法, 另一种就是从底而下的方法

题解

解法一 : 自顶而下

图解代码

实现思路

我们可以定义一个函数来求取我们二叉树中某一个节点的高度, 那我们的高度如何求取呢?

我们可以想到这么一个问题, 像是我们上图所示, 如果我们的这个点是空节点, 那么我们高度就是返回$00$, 如果不是的话, 就是看这个点的左右子树最大的高度 $+1+\; 1$, 然后我们不断的递归判断我们的左右子树是否满足条件, 根据这个思路就是可以写出来我们的这个代码

代码实现

class Solution {
   public:
    int dfs(TreeNode *root) {
        if (root == nullptr) return 0;
        // 如果是空节点直接返回0
        return max(dfs(root->left), dfs(root->right)) + 1;
        // 返回左右子树更高的那一颗树的高度然后加上当前这层的高度
    }
    bool IsBalanced_Solution(TreeNode *pRoot) {
        if (pRoot == nullptr) return true;
        // 如果是空节点返回true
        if (abs(dfs(pRoot->left) - dfs(pRoot->right)) <= 1 &&
            IsBalanced_Solution(pRoot->left) &&
            IsBalanced_Solution(pRoot->right)) {
                // 如果当前节点的左右子树都是满足条件的, 并且当前节点的左右子树的高度差不超过1. 就是可以的
            return true;
        } else {
            return false;
        }
    }
};

时空复杂度分析

时间复杂度: $O(n^2)O(n\; ^\; 2)$

理由如下: 如果我们是一个满二叉树, 我们是要遍历所有的节点, 那么我们的这个的复杂度就是$O(n)O(n)$的, 然后我们考虑一般的状态的话, 我们每一个点的深度也就是$loglog$级别的, 但是我们要考虑极限情况下, 我们退化成为一条链的时候, 我们的高度就会成为$nn$, 那么我们的时间复杂度就会退化成为$O(n^2)O(n\; ^\; 2)$

空间复杂度: $O(n)O(n)$

理由如下: 我们的空间要考虑系统递归栈调用的层数, 我们极限情况下退化成为一条链, 那么我们的空间复杂度就是$O(n)O(n)$的

解法二 : 自底而上

解题思路

如果我们先是遍历, 然后每次返回的是我们底下子树的高度, 然后我们去判断是否平衡, 如果我们这个树的某一个子树它是不平衡了, 我们可以得到整个子树其实都是不平衡的, 然后我们这样从底下开始判断, 如果底下的是成功的, 我们返回他的高度, 如果不平衡了, 我们直接可以返回不成功的办法, 就是用$-1-1$表示, 最后我们这样就可以把我们解法一的计算高度的函数重复的很多次数减少掉

代码解释

class Solution {
   public:
    int dfs(TreeNode *root) {
        if (root == nullptr) return 0;
        // 如果是空节点, 那么我们肯定是可以的, 我们返回0
        int l = dfs(root->left), r = dfs(root->right);
        // 我们得到我们的左右节点的高度
        if (l == -1 || r == -1 || abs(l - r) > 1) return -1;
        // 如果我们的左右高度是-1或者, 他俩的高度差大于了1, 我们也是返回-1
        return max(l, r) + 1;
        // 最后我们还是判断左右节点的最高那颗子树+1
    }
    bool IsBalanced_Solution(TreeNode *pRoot) {
        return dfs(pRoot) >= 0;
        // 我们判断我们是不是这个根节点满足条件
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们也就是遍历一次我们的所有的一个节点, 那么我们的时间复杂度就是$O(n)O(n)$

空间复杂度: $O(n)O(n)$

理由如下: 我们极限情况是退化成为一个链, 那么我们的递归栈的深度就是$O(n)O(n)$