[코딩인터뷰 완전정복] 4.9 BST 수열

Q : 배열의 원소를 왼쪽에서부터 차례로 트리에 삽입함으로써 이진 탐색 트리를 생성할 수 있다. 이진 탐색 트리 안에서 원소가 중복되지 않는다고 할 때, 해당 트리를 만들어 낼 수 있는 모든 가능한 배열을 출력하라.

 

 

Input : 이진 탐색 트리

output : 가능한 모든 입력 배열

 

배열의 원소를 왼쪽에서부터 차례로 삽입하는 경우 루트는 항상 첫번째 원소가 된다.

나머지 트리의 각 원소는 다음의 한가지 조건만 고려하면된다.

부모 노드는 자식 노드보다 먼저 나와야 한다.

왼쪽의 원소가 먼저 입력되냐 오른쪽의 원소가 먼저 입력되느냐는 중요하지 않다.

 

1. 트리를 탐색노드로 한다.

2. 탐색노드를 입력배열의 원소에 추가한다.

3. 트리의 자식들을 후보 리스트에 넣는다.

4. 입력배열과 후보 리스트를 넘겨주며, 후보 리스트의 원소들을 탐색노드로 하여 재귀호출한다.

5. 탐색이 종료되면 입력배열을 출력한다.

void BSTSequence(TreeNode<int>* root, std::queue<int> posibleInput, std::queue<TreeNode<int>*> nextNode) {
	posibleInput.push(root->data);
	if(root->left !=NULL)
		nextNode.push(root->left);
	if (root->right != NULL)
		nextNode.push(root->right);

	if (nextNode.size() == 0) {
		printf("[");
		while (posibleInput.size() != 0) {
			printf("%d, ", posibleInput.front());
			posibleInput.pop();
		}
		printf("]\n");
		return;
	}

	while(nextNode.size() != 0)
	{
		BSTSequence(nextNode.front() , posibleInput, nextNode);
		nextNode.pop();
	}
}