（13 分）已知一棵二叉树采用二叉链表存储，结点结构为：

root 指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过 1。例如下图所示的二叉树就是一棵平衡二叉树。

要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

复杂度分析 平衡二叉树

[tag_link]

【答案】

（1）基本设计思想：采用递归后序遍历二叉树，在计算每个结点高度的同时判断其左右子树是否平衡。递归函数返回当前子树的高度，若子树不平衡则返回 -1 作为标志。对于每个结点，先递归检查其左右子树，若任一子树返回 -1，则当前子树不平衡；否则计算左右子树高度差，若超过 1 则返回 -1，否则返回当前子树高度（即左右子树最大高度加 1）。最终，若根结点对应的递归返回值不为 -1，则二叉树是平衡的。

（2）算法描述（C 语言）： #include <stdlib.h> // 用于 abs 函数 #include <stdbool.h> // 用于 bool 类型 struct Node { struct Node * lchild ; int data ; struct Node * rchild ; }; // 辅助函数：检查以 root 为根的子树是否平衡，返回高度；若不平衡返回 -1 int checkBalance ( struct Node * root ) { if ( root == NULL ) { return 0 ; // 空树高度为 0，平衡 } // 递归检查左子树 int leftHeight = checkBalance ( root -> lchild ); if ( leftHeight == - 1 ) { return - 1 ; // 左子树不平衡，向上传递 } // 递归检查右子树 int rightHeight = checkBalance ( root -> rchild ); if ( rightHeight == - 1 ) { return - 1 ; // 右子树不平衡，向上传递 } // 检查当前结点左右子树高度差 if ( abs ( leftHeight - rightHeight ) > 1 ) { return - 1 ; // 当前结点不平衡 } // 返回当前子树高度 return ( leftHeight > rightHeight ? leftHeight : rightHeight ) + 1 ; } // 主函数：判断二叉树是否平衡 bool isBalanced ( struct Node * root ) { return checkBalance ( root ) != - 1 ; } 【解析】 该算法基于递归实现，核心思想是在计算结点高度时同步判断平衡性，避免重复遍历。checkBalance 函数采用后序遍历顺序：先递归处理左右子树，再处理当前结点。若子树不平衡（返回 -1），则立即向上返回，无需进一步计算；否则比较左右子树高度差，若超过 1 则返回 -1 表示不平衡，否则返回当前子树高度。isBalanced 函数通过调用 checkBalance 检查返回值是否为 -1 来判断整棵树的平衡性。算法中每个结点仅访问一次，时间复杂度为 O(n)，n 为结点数；递归栈空间复杂度为 O(h)，h 为树高。这种设计既高效又简洁，符合题目要求。