[코딩인터뷰 완전정복] 4.4 균형 확인

Q : 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다.

// Node.h

template <class T>
class TreeNode{
public:
	T data;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;

	TreeNode(T data) {
		this->data = data;
	}
};

#include <iostream>
#include "Node.h"

int checkBalanced(TreeNode<int>* top) {
	int left = top->left == NULL ? 1 : checkBalanced(top->left) + 1;
	int right = top->right == NULL ? 1 : checkBalanced(top->right) + 1;

	if (left==0 || right == 0 || abs(left - right) > 1) return -1;
	else return left < right ? right : left;
}

int main() {
	TreeNode<int> node_1(1);
	TreeNode<int> node_2(2);
	TreeNode<int> node_3(2);
	TreeNode<int> node_4(3);
	TreeNode<int> node_5(3);
	TreeNode<int> node_6(3);
	TreeNode<int> node_7(4);
	TreeNode<int> node_8(4);
	TreeNode<int> node_9(4);
	TreeNode<int> node_10(4);
	TreeNode<int> node_11(5);

	node_1.left = &node_2;
	node_1.right = &node_3;
	node_2.left = &node_4;
	node_2.right = &node_5;
	node_3.right = &node_6;
	node_4.left = &node_7;
	node_4.right = &node_8;
	node_5.left = &node_9;
	node_3.left = &node_10;
	node_10.right = &node_11;

	if(checkBalanced(&node_1)==-1)
		printf("Is not balenced");
	else
		printf("Is balenced");

}

이진 트리는 다음을 만족하면 균형 이진트리가 된다.

1. 좌,우의 subtree가 균형이진트리이며,

2. 좌,우 tree의 높이가 같다.

따라서 좌우의 트리에 대하여 균형 이진트리인지 확인하고, 균형 이진 트리인 경우, 그 높이를, 균형 이진 트리가 아닌 경우 -1을 리턴한다.

좌우의 높이가 1이상 차이가 나거나 한쪽이 균형 이진 트리가 아닐 경우 그 트리는 균형 이진트리가 아니다.