두 갈래 나무가 균형 있는 두 갈래 나무인지 아닌지를 판단하다

제목: 두 갈래 나무의 뿌리 노드를 입력하여 이 나무가 균형 있는 두 갈래 나무인지 판단한다.만약 어떤 두 갈래 나무 중 임의의 노드의 좌우 자목의 깊이 차이가 1을 넘지 않는다면, 그것은 바로 균형 두 갈래 나무이다.
각 노드가 한 번만 반복하는 해법:
뒷걸음질로 두 갈래 나무의 모든 노드를 훑어보았기 때문에, 한 노드를 훑어보기 전에 좌우 나무를 훑어보았다.따라서 모든 노드를 훑어볼 때 그 깊이를 기록하면 (어떤 노드의 깊이는 잎 노드까지의 경로 길이와 같다) 모든 노드가 균형적인지 아닌지를 훑어볼 수 있다.코드는 다음과 같습니다.

// 
#include<iostream>
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;
}

뒷걸음질로 두 갈래 나무를 두루 훑어보다.어떤 노드의 좌우 노드를 두루 훑어본 후에 그의 좌우 노드의 깊이에 따라 그것이 균형적인지 판단하고 현재 노드의 깊이를 얻을 수 있다.마지막으로 나무의 뿌리 노드를 두루 훑어보았을 때, 두 갈래 나무가 균형이 맞는지 아닌지를 판단한 것이다.