【本文鏈接】
http://www.cnblogs.com/hellogiser/p/is-balanced-tree.html
【題目】
輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1，那麼它就是一棵平衡二叉樹。例如下圖中的二叉樹就是一棵平衡二叉樹：
【方案2】 在判斷左右子樹是否平衡的過程中把深度計算出來，這樣在對父結點進行平衡判斷時就可以不用再重復計算左右子樹的深度了。其時間復雜度為O(n)。 【代碼】 【參考】 http://zhedahht.blog.163.com/blog/static/25411174201142733927831/ http://blog.csdn.net/zjull/article/details/11646591 http://blog.csdn.net/luckyxiaoqiang/article/details/7518888 【本文鏈接】 http://www.cnblogs.com/hellogiser/p/is-balanced-tree.html
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
*/
// binary tree node struct
struct BinaryTreeNode
{
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
// Get depth of a binary tree
int TreeDepth(BinaryTreeNode *root)
{
// the depth of a empty tree is 0
if(NULL == root)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(root->left);
// the depth of right sub-tree
int nRight = TreeDepth(root->right);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
// return max(nLeft,nRight)+1;
}
// is balanced tree in O(n^2)
bool IsBalanced(BinaryTreeNode *root)
{
if(NULL == root)
return true;
if(!IsBalanced(root->left))
return false;
if(!IsBalanced(root->right))
return false;
int leftDepth = TreeDepth(root->left);
int rightDepth = TreeDepth(root->right);
if (abs(leftDepth - rightDepth) > 1)
return false;
else
return true;
}
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
// is balanced tree in O(n)
bool IsBalanced(BinaryTreeNode *root, int &depth)
{
if(NULL == root)
{
depth = 0;
return true;
}
int leftDepth, rightDepth;
if(!IsBalanced(root->left, leftDepth))
return false;
if(!IsBalanced(root->right, rightDepth))
return false;
// get root depth without visiting left and right sub-trees
depth = (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
if (abs(leftDepth - rightDepth) > 1)
return false;
else
return true;
}
// is balanced tree
bool IsBalancedTree(BinaryTreeNode *root)
{
int depth;
return IsBalanced(root, depth);
}
