力扣第110题：平衡二叉树

力扣第110题：平衡二叉树

题目描述

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

高度平衡二叉树：一个二叉树，若每个节点的左右子树的高度差的绝对值不超过1，则该树是高度平衡的。

解题思路

为了判断二叉树是否为平衡二叉树，我们可以采用递归的方式，计算每个节点的左右子树的高度，并同时判断左右子树的高度差是否超过1。

1. 高度差判断：对于每个节点，左右子树的高度差不能超过1。
2. 递归计算高度：我们可以使用递归来计算左右子树的高度，并判断该节点是否平衡。递归的过程中，如果某个子树不平衡，我们可以直接返回 -1，表示该树不平衡。

解法步骤

1. 从根节点开始，递归地计算左右子树的高度。
2. 如果某个节点的左右子树的高度差大于1，则该树不平衡。
3. 如果递归到某个节点时，左右子树的高度差大于1，返回 -1，表示不平衡。
4. 如果树的每个节点都满足左右子树的高度差小于等于1，则该树是平衡的。

代码实现（C 语言）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 计算树的高度，如果树不平衡，返回 -1
int checkHeight(struct TreeNode* root) {
    // 空树的高度为 0
    if (root == NULL) {
        return 0;
    }

    // 递归计算左子树高度
    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) {
        return -1; // 如果左子树不平衡，直接返回 -1
    }

    // 递归计算右子树高度
    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) {
        return -1; // 如果右子树不平衡，直接返回 -1
    }

    // 判断当前节点的左右子树高度差
    if (abs(leftHeight - rightHeight) > 1) {
        return -1; // 如果高度差大于 1，返回 -1，表示不平衡
    }

    // 返回当前节点的高度
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

// 判断树是否为平衡二叉树
bool isBalanced(struct TreeNode* root) {
    return checkHeight(root) != -1;
}

// 辅助函数：创建树节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// 测试代码
int main() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->left = createNode(3);
    root->left->right = createNode(3);
    root->left->left->left = createNode(4);
    root->left->left->right = createNode(4);

    if (isBalanced(root)) {
        printf("The tree is balanced.\n");
    } else {
        printf("The tree is not balanced.\n");
    }

    return 0;
}

代码解析

1. 树结构：TreeNode 结构体定义了二叉树节点，包含节点值 val 和左右子树指针 left 和 right。
2. 计算高度并判断平衡：checkHeight 函数递归地计算树的高度，并判断树是否平衡。如果某个子树不平衡，则返回 -1，否则返回该节点的高度。
3. 平衡树判断：isBalanced 函数调用 checkHeight 来判断树是否平衡。如果 checkHeight 返回 -1，则表示树不平衡；否则表示树平衡。
4. 测试代码：在 main 函数中，我们构造了一个测试用例来检查树是否平衡，并输出结果。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树中的节点数。每个节点都被访问一次，且每次访问时都进行常数时间的操作。
• 空间复杂度：$O(h)$，其中 $h$ 是树的高度。递归深度为树的高度，因此空间复杂度为 $O(h)$。在最坏情况下（树退化成链表时），空间复杂度为 $O(n)$，但在平衡树情况下，空间复杂度为 $O(\log n)$。