【2024考研】题解25 | #判断是不是平衡二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    //算算深度
    int depth(TreeNode* root){
        if(root == NULL)
            return 0;
        int left = depth(root->left);
        int right = depth(root->right);
        return (left > right)? left + 1 : right + 1;
    }
  	//平衡树就是左右子树深度差的绝对值不超过1
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        if(pRoot == NULL) return true;

        int left = depth(pRoot->left);
        int right = depth(pRoot->right);

        if(abs(left - right) > 1) return false;

        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

基本算法思路：

- 使用递归的方式判断一棵二叉树是否是平衡二叉树。

- 首先判断特殊情况，如果根节点为空，则返回true。

- 定义一个递归函数depth，该函数接受当前节点作为参数，返回当前节点的深度。

- 如果当前节点为空，则返回0。

- 递归计算当前节点的左子树的深度和右子树的深度，取较大值加1作为当前节点的深度。

- 在递归函数IsBalanced_Solution中，计算当前节点的左子树的深度和右子树的深度。

- 如果左右子树的深度差的绝对值大于1，则返回false。

- 递归判断当前节点的左子树和右子树是否是平衡二叉树。

- 返回左子树和右子树的结果的逻辑与运算结果。

时间复杂度：

O(n^2)，其中n是二叉树的节点个数。每个节点都需要计算一次深度，计算深度的时间复杂度为O(n)，总共需要计算n个节点的深度，因此时间复杂度为O(n^2)。

空间复杂度：

O(n)，递归调用栈的深度最大为二叉树的高度，最坏情况下，二叉树是一个链表，高度为n，因此空间复杂度是O(n)。