C语言算法-解答平衡二叉树算法问题的C语言实现

题目

给定一棵二叉树，判断它是否是一棵平衡二叉树。平衡二叉树的定义是，对于树中的每个节点，其左子树和右子树的高度差不超过1。

引言

平衡二叉树是一种重要的二叉树结构，它可以提供快速的搜索、插入和删除操作。为了判断一棵二叉树是否为平衡二叉树，我们需要计算每个节点的左子树和右子树的高度，然后检查它们的高度差是否不超过1。

算法思路

1. 递归计算树的高度： 我们可以编写一个递归函数，计算树的高度。递归函数应该返回左子树和右子树中的最大高度，并将其加1作为当前节点的高度。
2. 检查每个节点： 对于每个节点，递归地计算左子树和右子树的高度，并检查它们的高度差是否不超过1。如果有任何节点不满足条件，树就不是平衡的。
3. 递归遍历整棵树： 我们从根节点开始递归遍历整棵树，检查每个节点是否满足平衡条件。
4. 返回结果： 如果整棵树都满足平衡条件，返回true；否则，返回false。

代码实现

以下是C语言中判断一棵二叉树是否为平衡二叉树的代码实现：

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

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 计算树的高度
int getHeight(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 判断是否为平衡二叉树
bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

算法分析

• 时间复杂度： 在每个节点上，我们需要递归计算左子树和右子树的高度。由于每个节点只被访问一次，所以时间复杂度为O(n)，其中n是二叉树的节点数。
• 空间复杂度： 递归调用的堆栈深度最多为树的高度，最坏情况下为O(n)。

示例和测试

int main() {
    // 构造一个平衡二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;

    bool result = isBalanced(root);
    if (result) {
        printf("是平衡二叉树\n");
    } else {
        printf("不是平衡二叉树\n");
    }

    return 0;
}

这段代码将构造一个平衡二叉树，然后使用isBalanced函数来判断它是否是平衡二叉树。

总结

判断一棵二叉树是否为平衡二叉树需要递归地计算每个节点的左子树和右子树的高度，并检查它们的高度差是否不超过1。这个算法的时间复杂度为O(n)，空间复杂度为O(n)，因为它递归地遍历整棵树并使用堆栈。在实际应用中，这个算法可以用于检查树的平衡性，以保持搜索、插入和删除等操作的高效性。