LeetCode面试题04 检查平衡性

标签：面试题 TreeNode struct 04 LeetCode 二叉树 return root 节点

题目：

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

一、平衡树定义：

二叉树，一种由节点组成的树形数据结构，每个节点最多有两个子节点，分别称作左子节点和右子节点。而平衡二叉树，可不是普通的二叉树，它有着严苛的要求：对于树中的任意一个节点，其两棵子树（左子树和右子树）的高度差不能超过 1。这个定义看似简单，实则暗藏玄机，它关乎二叉树的查找效率、稳定性等诸多性能指标。想象一下，如果一棵二叉树极度不平衡，就如同瘸腿走路，某些操作的耗时会大幅增加，效率大打折扣。

举个例子，在一棵平衡二叉搜索树里，查找一个元素的时间复杂度接近O( $\log n$ )。可要是树失衡了，最坏情况下查找时间复杂度能退化成O（ $n$ ），这差距可就太悬殊了。

二、解题思路拆解

整体思路概述

拿到这道题，要判断一棵二叉树是否平衡，关键在于检查树中每个节点的左右子树高度差是否都不超过 1。所以整体思路是通过遍历二叉树的每个节点，去获取并比较其左右子树的高度，进而得出整棵树是否平衡的结论，通常会采用递归的方式来实现这个过程。

（一）计算子树高度

咱们得先打造一个 “高度测量仪”，也就是一个专门计算以某个节点为根节点的子树高度的函数。递归在这里大展拳脚，其逻辑简洁而巧妙：当节点为空时，好比遇到了树的 “尽头”，高度自然是 0；要是节点非空，那这棵子树的高度就得看它左右 “臂膀”（左右子树）谁更长了，取两者高度最大值，再给它加上 1（把当前节点这一层算上）。以下是用 C 语言展示的代码片段：

//计算树的高度的辅助函数
int treeHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int leftHeight = treeHeight(node->left);
    int rightHeight = treeHeight(node->right);
    return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}

在这段代码里，先是递归地深挖 node 的左子树高度存进 leftHeight，再探寻右子树高度存入 rightHeight，最后掐指一算，挑出大值加 1 返回，完美算出子树高度。

（二）判断节点平衡性与整树遍历

有了测量子树高度的 “神器”，下一步就是打造主函数来宣判二叉树的 “平衡命运” 了。首先要照顾到特殊情况，要是根节点就是空的，那没得说，这棵树妥妥是平衡的，直接返回 true，皆大欢喜。

碰上根节点非空时，就得严肃起来了。先用刚才的函数量出根节点左右子树各自的高度，要是这俩高度差的绝对值大于 1，那这棵树在根节点这儿就 “崴脚” 了，立马返回 false，宣判它不平衡。

但事情还没完，即便当前根节点这关过了，它的子树里说不定还有 “定时炸弹” （不平衡的节点）呢。所以得接着递归调用主函数，分别去审查左子树和右子树是否平衡，只有左右子树都稳稳当当、符合平衡标准，这整棵树才算得上是平衡的，故而最终返回对左右子树递归判断结果的逻辑与（&&）。用代码说话：

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

三、代码实现

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

//定义树的结构体
struct TreeNode {

      int val;
      struct TreeNode *left;
      struct TreeNode *right;
};


// 构建二叉树节点的函数（辅助函数，方便创建测试用的二叉树）
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 计算树的高度的辅助函数
int treeHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    // 递归计算左子树高度
    int leftHeight = treeHeight(node->left);
    // 递归计算右子树高度
    int rightHeight = treeHeight(node->right);
    // 取左右子树中较大的高度加1（根节点算一层）作为当前节点所在子树的高度
    return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}


bool isBalanced (struct TreeNode* root)
{
    if (root==NULL){
        return true;
    }
    // 计算左子树高度
    int leftHeight = treeHeight(root->left);
    // 计算右子树高度
    int rightHeight = treeHeight(root->right);
    // 判断当前节点的左右子树高度差是否超过1，若超过则不平衡
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    // 递归地判断左子树和右子树是否平衡
    return isBalanced(root->left) && isBalanced(root->right);
};

int main(){
//构建一个二叉树
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left=createNode(15);
    root->right->right=createNode(7);

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

    return 0;
}

四、代码实现细节与优化点

上面给出的代码是基于 C 语言结构体实现二叉树节点的经典范例。代码结构清晰，两个函数各司其职，一个专心算高度，一个全力判断平衡。

不过呢，这代码还有优化空间。现在计算子树高度和判断平衡的过程中存在重复计算，每次判断一个节点的平衡性，都要重新完整计算左右子树高度，当树规模大时，计算量冗余严重。优化思路是把高度计算与平衡判断合二为一，一边计算高度一边检查平衡性，一旦发现不平衡就及时止损，不再做无用功。这种改进能大幅削减不必要的计算，提升算法效率。

五、改进代码实现

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

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

// 构建二叉树节点的函数（辅助函数，方便创建测试用的二叉树）
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 优化后的函数，同时计算高度并判断是否平衡，返回值大于等于0表示当前子树的高度，返回 -1表示子树不平衡
int isBalancedAndHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    // 递归计算左子树高度并判断平衡性
    int leftHeight = isBalancedAndHeight(node->left);
    if (leftHeight == -1) {
        return -1;
    }
    // 递归计算右子树高度并判断平衡性
    int rightHeight = isBalancedAndHeight(node->right);
    if (rightHeight == -1) {
        return -1;
    }
    // 检查当前节点的左右子树高度差是否超过1
    if (abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    // 返回当前子树高度（左右子树中较大高度 + 1）
    return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}

// 判断二叉树是否平衡的主函数，调用优化后的辅助函数进行判断
bool isBalanced(struct TreeNode* root) {
    return isBalancedAndHeight(root)!= -1;
}

int main() {
    // 构建一个简单的二叉树示例（这里你可以自行修改节点值和结构来测试不同情况）
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left=createNode(15);
    root->right->right=createNode(7);


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

    return 0;
}

总结与拓展

判断二叉树是否平衡不仅是一道算法面试高频题，更是深入理解二叉树特性的绝佳契机。通过递归手段巧妙遍历、精准测量、严谨比对，我们能稳稳拿捏二叉树的平衡状况。往后再遇到二叉树相关复杂操作，像是构建平衡二叉搜索树、优化树的存储与查找等，这判断平衡的技巧都能派上大用场。

掌握了二叉树平衡判断，就像是拿到了二叉树世界的一把钥匙，诸多神秘大门将徐徐向你敞开。不管是继续刷题深造，还是实际项目里优化数据结构，都能底气十足、游刃有余。要是你对这篇博客内容有啥疑问、想法，或是独到见解，欢迎随时留言交流，咱们一起在算法海洋破浪前行！

标签：面试题,TreeNode,struct,04,LeetCode,二叉树,return,root,节点
From： https://blog.csdn.net/qq_64604732/article/details/144377706