大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 2种方法判断二叉树是不是平衡二叉树

2种方法判断二叉树是不是平衡二叉树

关键词:判断二叉树平衡二叉树  阅读(3287) 赞(20)

[摘要]本文是对2种方法判断二叉树是不是平衡二叉树的讲解,对学习C++编程技术有所帮助,与大家分享。
【题目】

输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树:

【分析】

之前的博文27.二元树的深度[BinaryTreeDepth]中介绍过如何求二叉树的深度。有了经验之后再解决这个问题,我们很容易就能想到思路。

【方案1】

先判断左右子树是不是平衡的,若平衡再求出左右子树的深度,若深度之差大于1,则不平衡。因为在遍历每个结点时都要求其左右子树的深度,因此时间复杂度是O(n^2)的。

【代码】

C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include"stdafx.h"
#include<cmath>
#include<algorithm>

/*
version:1.0
author:hellogiser
blog:http://www.cnblogs.com/hellogiser
date:2014/5/25
*/

//binarytreenodestruct
structBinaryTreeNode
{
intvalue;
BinaryTreeNode*left;
BinaryTreeNode*right;
};

//Getdepthofabinarytree
intTreeDepth(BinaryTreeNode*root)
{
//thedepthofaemptytreeis0
if(NULL==root)
return0;

//thedepthofleftsub-tree
intnLeft=TreeDepth(root->left);
//thedepthofrightsub-tree
intnRight=TreeDepth(root->right);

//depthisthebinarytree
return(nLeft>nRight)?(nLeft+1):(nRight+1);
//returnmax(nLeft,nRight)+1;
}

//isbalancedtreeinO(n^2)
boolIsBalanced(BinaryTreeNode*root)
{
if(NULL==root)
returntrue;
if(!IsBalanced(root->left))
returnfalse;
if(!IsBalanced(root->right))
returnfalse;
intleftDepth=TreeDepth(root->left);
intrightDepth=TreeDepth(root->right);
if(abs(leftDepth-rightDepth)>1)
returnfalse;
else
returntrue;
}

【方案2】

在判断左右子树是否平衡的过程中把深度计算出来,这样在对父结点进行平衡判断时就可以不用再重复计算左右子树的深度了。其时间复杂度为O(n)。

【代码】

C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//isbalancedtreeinO(n)
boolIsBalanced(BinaryTreeNode*root,int&depth)
{
if(NULL==root)
{
depth=0;
returntrue;
}

intleftDepth,rightDepth;
if(!IsBalanced(root->left,leftDepth))
returnfalse;
if(!IsBalanced(root->right,rightDepth))
returnfalse;

//getrootdepthwithoutvisitingleftandrightsub-trees
depth=(leftDepth>rightDepth)?(leftDepth+1):(rightDepth+1);
if(abs(leftDepth-rightDepth)>1)
returnfalse;
else
returntrue;
}

//isbalancedtree
boolIsBalancedTree(BinaryTreeNode*root)
{
intdepth;
returnIsBalanced(root,depth);
}


相关评论