判断二叉树是否是平衡二叉树【C++版】

判断二叉树是否是平衡二叉树【C++版】

1.题意

给出一个BST的先序遍历序列，你需要判断这个BST是否是平衡二叉树。

2.分析

• step 1: 根据BST的先序序列，我们可以构建一棵完整的BST
• step 2:根据得到的BST，我们可以使用递归的手法检查这棵树是否是一棵平衡二叉树，递归的思想如下：
  递归查找每个根节点的左子树的高度lLen，右子树高度rLen，然后判断这个abs(rLen-lLen)与1的大小关系即可。同时我们使用一个标记变量balanFlag最后在main中判断一下即可。

3.实现

#include<cstdio> 
#include<algorithm>
#include<iostream>
#define maxn 35
using namespace std;

struct node{
	node* lchild;
	node* rchild;
	int data;
	int level;//层次【从上到下】 
	int height;//高度【从下到上 root的高度最高】 
};

int pre[maxn] ;
int in[maxn];
bool balanFlag=true;//标志是否是平衡 

node* create(int preL,int preR,int inL,int inR){
	if(preL > preR) return NULL;
	node* root = new node;
	root->data = abs(pre[preL]);//因为有负号的情况 
	int i;
	for(i = 0;i< inR;i++){
		if(in[i] == abs(pre[preL])) break;
	}
	int numLeft = i - inL;
	root->lchild = create(preL+1,preL+numLeft,inL,i-1);
	root->rchild = create(preL+numLeft+1,preR,i+1,inR);
	return root;
}
 
//获取以root为根节点的子树的当前height
int getHeight(node* root) {
	if(root == NULL) return 0;
	else { 
		return  max(getHeight(root->lchild),getHeight(root->rchild)) + 1;
	}
}

//判断是否平衡 
void isBalance(node* root){	
	int lLen = getHeight(root->lchild);
	int rLen = getHeight(root->rchild);
	if(abs(lLen - rLen ) > 1)	{
		balanFlag = false; 
		return ;//不是平衡树
	}	
}

int main(){
	int K,N;
	cin >> K ;
	int i,j;
	while(K--){
		cin >>N;
		fill(pre,pre+N,0);//重置为0
		fill(in,in+N,0);//重置为0
		balanFlag = true;//初始化为平衡二叉树 
		for(i = 0;i< N;i++){
			cin >> pre[i];
			in[i] = abs(pre[i]);
		}
		sort(in,in+N);//排序
		node* root = create(0,N-1,0,N-1);					
		
		isBalance(root); 
		if(balanFlag){//判断是否平衡	
			cout <<"balance\n"; 
		}
		else{
			cout <<"not balance\n";
		}
	}
}

4.测试用例

3
9
7 2 1 5 4 11 8 14 15
9
11 2 1 7 5 4 8 14 15
8
10 7 5 6 8 15 11 17

针对上述的三个测试用例，构建得到的二叉树如下所示：

5.执行结果