题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1 ，那么它就是一棵平衡二叉树。

每个节点只遍历一次的解法：

    由于当使用后序遍历的方式遍历二叉树的每一个节点，在遍历到一个节点之前已经遍历了它的左右子树。因此，只要在遍历每个节点的时候记录它的深度（某一节点的深度等于它到叶子节点的路径长度），就可以一边遍历一边判断每个节点是不是平衡的。代码如下：

//判断一棵二叉树是不是为一棵平衡二叉树#include
    
     using namespace std;typedef int ElemType;typedef struct TNode{	ElemType value;	struct TNode *pLeftChild;	struct TNode *pRightChild;}TreeNode, *BinaryTree;TreeNode* CreateTreeNode(ElemType e){	TreeNode *pNode = new TreeNode();	pNode->value = e;	pNode->pLeftChild = NULL;	pNode->pRightChild = NULL;	return pNode;}void ConnectionTreeNode(TreeNode *pParent, TreeNode *pLeft, TreeNode *pRight){	if(pParent == NULL)		return;	pParent->pLeftChild = pLeft;	pParent->pRightChild = pRight;}TreeNode* CreateBinaryTree(){	TreeNode *pNode1 = CreateTreeNode(1);	TreeNode *pNode2 = CreateTreeNode(2);	TreeNode *pNode3 = CreateTreeNode(3);	TreeNode *pNode4 = CreateTreeNode(4);	TreeNode *pNode5 = CreateTreeNode(5);	TreeNode *pNode6 = CreateTreeNode(6);	TreeNode *pNode7 = CreateTreeNode(7);		ConnectionTreeNode(pNode1, pNode2, pNode3);	ConnectionTreeNode(pNode2, pNode4, pNode5);	//ConnectionTreeNode(pNode3, NULL, pNode6);	ConnectionTreeNode(pNode5, pNode7, NULL);	//ConnectionTreeNode(pNode1, NULL, NULL);	return pNode1;}bool IsBalanced(TreeNode *pRoot, int *pDepth){	if(pRoot == NULL)	{		*pDepth = 0;		return true;	}	int left, right;	if(IsBalanced(pRoot->pLeftChild, &left)		&& IsBalanced(pRoot->pRightChild, &right))	{		int diff = left - right;		if(diff <= 1 && diff >= -1)		{			*pDepth = (left > right) ? (left + 1) : (right + 1);			return true;		}	}	return false;}bool IsBinaryTreeBalanced(TreeNode *pRoot){	int depth = 0;	return IsBalanced(pRoot, &depth);}int main(){	TreeNode *pNode = CreateBinaryTree();	bool result = IsBinaryTreeBalanced(pNode);	if(result)		cout << "这是一棵平衡二叉树！！" << endl;	else		cout << "这不是一棵平衡二叉树！！" << endl;	system("pause");	return 0;}
    

    用后序遍历的方式遍历整棵二叉树。在遍历某节点的左右子节点之后，可以根据它的左右子节点的深度判断它是不是平衡的，并得到当前节点的深度。当最后遍历到树的根节点的时候，也就是判断了一棵二叉树是不是平衡的。