题目：编程题-平衡二叉树
时间限制 1000 ms，内存限制 256000 kB，代码长度限制 8000 B判断一个二叉树是不是平衡说明：一棵二叉树任意一个节点的左右子树的深度差不大于1，即为平衡二叉树。给定一个有N个节点的二叉树，每个节点有一个序号表示，树有M条分支。每个分支用三个数字A B C表示，指A节点的左儿子为B，右儿子为C。如果B或C为-1，说明无该儿子。规定树根的序号为1，树的节点数目最多不超过50000。每个测试数据有多组case。对于每个case，第一行先输入N和M。然后下面M行每行代表一个分支。对于每个case输出为一行，如果该树是平衡二叉树，请输出1，否则输出0每个case之间不需要空行隔开，如以下示例输入示例11 55 6 74 10 113 8 91 2 32 4 513 66 7 82 3 410 11 128 9 101 2 134 5 6输出示例10
分析：题目可以分解成两个问题：
1、根据输入数据组织二叉树；
2、判断平衡二叉树。
针对问题1：由于每个结点序号已事先固定，可以使用数组来表示，数组下标即为结点序号。对于每个结点的左右孩子的表示，可以定义两个数组，分别是leftChild[]左孩子数组，rightChild[]右孩子数组，结点i的左孩子为leftChild[i]，右孩子为rightChild[i]；也可以定义一个结构体 struct Node {int leftChild; int rightChild;}，再定义结点数组biTree[]，如此结点i的左右孩子即为biTree[i].leftChild,
biTree[i].rightChild。
biTree[i].rightChild。
#include <stdio.h>
#include <queue>
struct Node {
int leftChild;
int rightChild;
Node() {
leftChild = -1;
rightChild = -1;
}
};
针对问题2：参考《剑指Offer》有两种方法，
方法一：判断二叉树是否平衡与求取每个结点的深度分离，此方法简单直观，但效率不高，每个结点在判断平衡和求取深度的时候都被重复遍历
int DepthOfBiTree(Node biTree[], int i) {
int leftDepth, rightDepth;
if (i == -1)
return 0;
leftDepth = 1 + DepthOfBiTree(biTree, biTree[i].leftChild);
rightDepth = 1 + DepthOfBiTree(biTree, biTree[i].rightChild);
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
bool IsBalanceBiTree(Node biTree[], int i) {
if (i == -1)
return true;
int diff = DepthOfBiTree(biTree, biTree[i].leftChild)
- DepthOfBiTree(biTree, biTree[i].rightChild);
if (diff > 1 || diff < -1)
return false;
else
return IsBalanceBiTree(biTree, biTree[i].leftChild)
&& IsBalanceBiTree(biTree, biTree[i].rightChild);
}
方法二：判断二叉树是否平衡和求取结点深度统一，此时避免了上面的问题
bool IsBalanceBiTree(Node biTree[], int i, int *depth) {
if (i == -1) {
*depth = 0;
return true;
}
int leftDepth, rightDepth;
if (IsBalanceBiTree(biTree, biTree[i].leftChild, &leftDepth)
&& IsBalanceBiTree(biTree, biTree[i].rightChild, &rightDepth)) {
int diff = leftDepth - rightDepth;
if (diff >= -1 && diff <= 1) {
*depth = 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
return true;
}
}
return false;
}
bool IsBalanceBiTree(Node biTree[]) {
int depth = 0;
return IsBalanceBiTree(biTree, 1, &depth);
}
读取数据的函数，以（0，0）结束：
void ReadData() {
std::queue<bool> result;
while (true) {
int N, M;
if (scanf("%d %d", &N, &M) != 2) break;
if (N <= 0 || M <= 0) break;
Node *biTree = new Node[N + 1];
int parent, leftChild, rightChild;
for (int i = 0 ; i < M; ++ i) {
scanf("%d %d %d", &parent, &leftChild, &rightChild);
biTree[parent].leftChild = leftChild;
biTree[parent].rightChild = rightChild;
}
if (IsBalanceBiTree(biTree))
result.push(true);
else
result.push(false);
delete[] biTree;
biTree = NULL;
}
while (!result.empty()) {
printf("%d\n", result.front());
result.pop();
}
}
PS：有道，机试，2013，校招