判断一个二叉树是否是平衡二叉树

题目：判断一个二叉排序树是否是平衡二叉树思路:利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树。#include<stdio.h>
#include "stdafx.h"struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};BinaryTreeNode* CreateBinaryTreeNode（int value）
{
BinaryTreeNode* pNode = new BinaryTreeNode（）;
pNode->m_nValue = value;
pNode->m_pLeft = NULL;
pNode->m_pRight = NULL;
}void ConnectTreeNodes（BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight）
{
if（pParent ！= NULL）
{
pParent->m_pLeft = pLeft;
pParent->m_pRight = pRight;
}
}void PrintTreeNode（BinaryTreeNode* pNode）
{
if（pNode ！= NULL）
{
printf（"value of this node is: %d ", pNode->m_nValue）;

if（pNode->m_pLeft ！= NULL）
printf（"value of its left child is: %d. ", pNode->m_pLeft->m_nValue）;
else
printf（"left child is null. "）;

if（pNode->m_pRight ！= NULL）
printf（"value of its right child is: %d. ",pNode->m_pRight->m_nValue）;
else
printf（"right child is null. "）;
}
else
{
printf（"this node is null. "）;
}
printf（" "）;
}void PrintTree（BinaryTreeNode* pRoot）
{
PrintTreeNode（pRoot）;

if（pRoot ！= NULL）
{
if（pRoot->m_pLeft ！= NULL）
PrintTree（pRoot->m_pLeft）;

if（pRoot->m_pRight ！= NULL）
PrintTree（pRoot->m_pRight）;
}
}void DestroyTree（BinaryTreeNode* pRoot）
{
if（pRoot ！= NULL）
{
BinaryTreeNode* pLeft = pRoot->m_pLeft;
BinaryTreeNode* pRight = pRoot->m_pRight;

delete pRoot;
pRoot = NULL;

DestroyTree（pLeft）;
DestroyTree（pRight）;
}
}
//========================方法1==============================
int TreeDepth（BinaryTreeNode* pRoot）
{
if（pRoot == NULL）
return 0;

int nLeft = TreeDepth（pRoot->m_pLeft）;
int nRight = TreeDepth（pRoot->m_pRight）;

return （nLeft > nRight）？（nLeft + 1） : （nRight + 1）;
}bool IsBalanced_Solution1（BinaryTreeNode* pRoot）
{
if（pRoot == NULL）
return true;

int left = TreeDepth（pRoot->m_pLeft）;
int right = TreeDepth（pRoot->m_pRight）;
int diff = left - right;
if（diff > 1 || diff < -1）
return false;

return IsBalanced_Solution1（pRoot->m_pLeft）
&& IsBalanced_Solution1（pRoot->m_pRight）;
}//=====================方法2===========================
bool IsBalanced（BinaryTreeNode* pRoot, int* pDepth）;bool IsBalanced_Solution2（BinaryTreeNode* pRoot）
{
int depth = 0;
return IsBalanced（pRoot, &depth）;
}bool IsBalanced（BinaryTreeNode* pRoot, int* pDepth）
{
if（pRoot == NULL）
{
*pDepth = 0;
return true;
}

int left, right;
if（IsBalanced（pRoot->m_pLeft, &left）
&& IsBalanced（pRoot->m_pRight, &right））
{
int diff = left - right;
if（diff <= 1 && diff >= -1）
{
*pDepth = 1+ （left > right ？ left : right）;
return true;
}
}

return false;
}// 不是完全二叉树，但是平衡二叉树
// 1
// /
// 2 3
// /
// 4 5 6
// /
// 7int main（）
{
BinaryTreeNode* pNode1 = CreateBinaryTreeNode（1）;
BinaryTreeNode* pNode2 = CreateBinaryTreeNode（2）;
BinaryTreeNode* pNode3 = CreateBinaryTreeNode（3）;
BinaryTreeNode* pNode4 = CreateBinaryTreeNode（4）;
BinaryTreeNode* pNode5 = CreateBinaryTreeNode（5）;
BinaryTreeNode* pNode6 = CreateBinaryTreeNode（6）;
BinaryTreeNode* pNode7 = CreateBinaryTreeNode（7）; ConnectTreeNodes（pNode1, pNode2, pNode3）;
ConnectTreeNodes（pNode2, pNode4, pNode5）;
ConnectTreeNodes（pNode3, pNode6, pNode7）;

printf（"Solution1 begins: "）;
if（IsBalanced_Solution1（pNode1））
printf（"is balanced. "）;
else
printf（"not balanced. "）;

printf（"Solution2 begins: "）;
if（IsBalanced_Solution2（pNode1））
printf（"is balanced. "）;
else
printf（"not balanced. "）;
printf（" "）;

DestroyTree（pNode1）;

return 0;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/132842.htm