BST – Keep on Coding

이진트리가 주어지면, 그것이 이진탐색트리인지 감별하는 메소드를 만든다.

이진트리와 이진탐색트리를 구별해야 한다. 이진트리와 이진탐색트리를 간단히 정리하자면..

이진트리:

이진탐색트리:

이진트리이면서..
모든 노드의 값은 해당 노드의 모든 왼쪽 자식들의 값보다 커야 함
모든 노드의 값은 해당 노드의 모든 오른쪽 자식들의 값보다 작아야 함
같은 값을 허용하는가는 정의 하기 나름 (본 문제에서는 같은 값은 없다고 정의했다)
이진트리지만 이진탐색트리는 아님 (이미지 출처: 위키피디아)

다음과 같이 이진탐색트리를 판정하는 코드를 만들었다.

	/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.

	The Node class is defined as follows:
	class Node {
	int data;
	Node left;
	Node right;
	}
	*/
	boolean checkBST(Node root) {
	if (root.left == null && root.right == null) {
	return true;
	} else {
	if (checkBST(root.left) && checkBST(root.right)) {
	int leftTreeMaxValue = treeMaxValue(root.left);
	int rightTreeMinValue = treeMinValue(root.right);
	if (leftTreeMaxValue < root.data && root.data < rightTreeMinValue) {
	return true;
	} else {
	return false;
	}
	} else {
	return false;
	}
	}
	}
	int treeMaxValue(Node root) {
	if (root.left == null && root.right == null) {
	return root.data;
	} else {
	int leftValue = treeMinValue(root.left);
	int value = root.data;
	int rightValue = treeMinValue(root.right);

	if (leftValue < value) {
	if (value < rightValue) {
	return rightValue;
	} else {
	return value;
	}
	} else {
	if (leftValue < rightValue) {
	return rightValue;
	} else {
	return leftValue;
	}
	}
	}
	}
	int treeMinValue(Node root) {
	if (root.left == null && root.right == null) {
	return root.data;
	} else {
	int leftValue = treeMinValue(root.left);
	int value = root.data;
	int rightValue = treeMinValue(root.right);

	if (leftValue > value) {
	if (value > rightValue) {
	return rightValue;
	} else {
	return value;
	}
	} else {
	if (leftValue > rightValue) {
	return rightValue;
	} else {
	return leftValue;
	}
	}
	}
	}

view raw check-BST.java hosted with ❤ by GitHub

이진트리를 구별하는 코드는 별로 어렵지 않았지만 그 안에 이진탐색트리 조건을 같이 담는 과정이 조금 까다로웠다.

Keep on Coding