思路:利用遞歸判斷左右子樹的深度是否相差1來判斷是否是平衡二叉樹。
1 #include<stdio.h>
2 #include "stdafx.h"
3
4 struct BinaryTreeNode
5 {
6 int m_nValue;
7 BinaryTreeNode* m_pLeft;
8 BinaryTreeNode* m_pRight;
9 };
10
11 BinaryTreeNode* CreateBinaryTreeNode(int value)
12 {
13 BinaryTreeNode* pNode = new BinaryTreeNode();
14 pNode->m_nValue = value;
15 pNode->m_pLeft = NULL;
16 pNode->m_pRight = NULL;
17 }
18
19 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
20 {
21 if(pParent != NULL)
22 {
23 pParent->m_pLeft = pLeft;
24 pParent->m_pRight = pRight;
25 }
26 }
27
28 void PrintTreeNode(BinaryTreeNode* pNode)
29 {
30 if(pNode != NULL)
31 {
32 printf("value of this node is: %d\n", pNode->m_nValue);
33
34 if(pNode->m_pLeft != NULL)
35 printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
36 else
37 printf("left child is null.\n");
38
39 if(pNode->m_pRight != NULL)
40 printf("value of its right child is: %d.\n",pNode->m_pRight->m_nValue);
41 else
42 printf("right child is null.\n");
43 }
44 else
45 {
46 printf("this node is null.\n");
47 }
48 printf("\n");
49 }
50
51 void PrintTree(BinaryTreeNode* pRoot)
52 {
53 PrintTreeNode(pRoot);
54
55 if(pRoot != NULL)
56 {
57 if(pRoot->m_pLeft != NULL)
58 PrintTree(pRoot->m_pLeft);
59
60 if(pRoot->m_pRight != NULL)
61 PrintTree(pRoot->m_pRight);
62 }
63 }
64
65 void DestroyTree(BinaryTreeNode* pRoot)
66 {
67 if(pRoot != NULL)
68 {
69 BinaryTreeNode* pLeft = pRoot->m_pLeft;
70 BinaryTreeNode* pRight = pRoot->m_pRight;
71
72 delete pRoot;
73 pRoot = NULL;
74
75 DestroyTree(pLeft);
76 DestroyTree(pRight);
77 }
78 }
79
80
81 //========================方法1==============================
82 int TreeDepth(BinaryTreeNode* pRoot)
83 {
84 if(pRoot == NULL)
85 return 0;
86
87 int nLeft = TreeDepth(pRoot->m_pLeft);
88 int nRight = TreeDepth(pRoot->m_pRight);
89
90 return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
91 }
92
93 bool IsBalanced_Solution1(BinaryTreeNode* pRoot)
94 {
95 if(pRoot == NULL)
96 return true;
97
98 int left = TreeDepth(pRoot->m_pLeft);
99 int right = TreeDepth(pRoot->m_pRight);
100 int diff = left - right;
101 if(diff > 1 || diff < -1)
102 return false;
103
104 return IsBalanced_Solution1(pRoot->m_pLeft)
105 && IsBalanced_Solution1(pRoot->m_pRight);
106 }
107
108 //=====================方法2===========================
109 bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth);
110
111 bool IsBalanced_Solution2(BinaryTreeNode* pRoot)
112 {
113 int depth = 0;
114 return IsBalanced(pRoot, &depth);
115 }
116
117 bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
118 {
119 if(pRoot == NULL)
120 {
121 *pDepth = 0;
122 return true;
123 }
124
125 int left, right;
126 if(IsBalanced(pRoot->m_pLeft, &left)
127 && IsBalanced(pRoot->m_pRight, &right))
128 {
129 int diff = left - right;
130 if(diff <= 1 && diff >= -1)
131 {
132 *pDepth = 1+ (left > right ? left : right);
133 return true;
134 }
135 }
136
137 return false;
138 }
139
140 // 不是完全二叉樹，但是平衡二叉樹
141 // 1
142 // / \
143 // 2 3
144 // /\ \
145 // 4 5 6
146 // /
147 // 7
148
149 int main()
150 {
151 BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
152 BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
153 BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
154 BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
155 BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
156 BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
157 BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
158
159 ConnectTreeNodes(pNode1, pNode2, pNode3);
160 ConnectTreeNodes(pNode2, pNode4, pNode5);
161 ConnectTreeNodes(pNode3, pNode6, pNode7);
162
163 printf("Solution1 begins: ");
164 if(IsBalanced_Solution1(pNode1))
165 printf("is balanced.\n");
166 else
167 printf("not balanced.\n");
168
169 printf("Solution2 begins: ");
170 if(IsBalanced_Solution2(pNode1))
171 printf("is balanced.\n");
172 else
173 printf("not balanced.\n");
174 printf("\n");
175
176 DestroyTree(pNode1);
177
178 return 0;
179 }
180
