题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
目前
成都创新互联已为数千家的企业提供了网站建设、域名、
虚拟主机、网站托管、
服务器租用、企业网站设计、
镇坪网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一个思路：在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下：
bool IsBalanced(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(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);
}上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树，首先判断根结点（值为1的结点）的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点（值为2的结点），需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。
如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。
#include
#include
using namespace std;
struct BinaryTreeNode
{
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x)
:data(x)
, left(NULL)
, right(NULL)
{}
};
class BinaryTree
{
protected:
BinaryTreeNode* _root;
BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
{
BinaryTreeNode* root = NULL;
if (index < size&&arr[index] != '#')
{
root = new BinaryTreeNode(arr[index]);
root->left = _CreateBinaryTree(arr, ++index, size);
root->right = _CreateBinaryTree(arr, ++index, size);
}
return root;
}
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(int *arr, int size)
{
int index = 0;
_root = _CreateBinaryTree(arr, index, size);
}
bool IsBalance()
{
int depth = 0;
return _IsBalance(_root, depth);
}
int Height()
{
return _Height(_root);
}
void PreOrder_Non()
{
if (_root == NULL)
return;
BinaryTreeNode* cur = _root;
stack s;
s.push(_root);
while (!s.empty())
{
cur = s.top();
printf("%d ", cur->data);
s.pop();
if (cur->right)
s.push(cur->right);
if (cur->left)
s.push(cur->left);
}
cout << endl;
}
protected:
int _Height(BinaryTreeNode* root)
{
if (root == NULL)
return 0;
int left = _Height(root->left);
int right = _Height(root->right);
return left > right ? left + 1 : right + 1;
}
bool _IsBalance(BinaryTreeNode* root, int& depth)
{
if (root == NULL)
return true;
int left, right;
if (_IsBalance(root->left, left) && _IsBalance(root->right, right))
{
int dif = left - right;
if (dif <= 1 && dif >= -1)
{
depth = left > right ? left + 1 : right + 1;
return true;
}
}
return false;
}
};
int main()
{
int a[] = { 1,2,3,'#','#','#'};
BinaryTree t(a,sizeof(a)/sizeof(a[0]));
t.PreOrder_Non();
cout<在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树了。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网页标题：后序遍历求解判断一颗二叉树是否为平衡二叉树-创新互联
本文路径：http://bzwzjz.com/article/csopdh.html
