[코딩인터뷰 완전정복] 4.5 BST 검증

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"

bool isBST(TreeNode<int>* top, int low, int high) {
	if (top == NULL) return true;
	if (low != NULL && top->data <= low) return false;
	if (high != NULL && top->data >= high) return false;
	bool left = isBST(top->left, low, top->data);
	bool right = isBST(top->right, top->data, high);
	return left && right;
}

int main() {
	TreeNode<int> a(10);
	TreeNode<int> b(5);
	TreeNode<int> c(15);
	TreeNode<int> d(3);
	TreeNode<int> e(7);
	TreeNode<int> f(13);
	TreeNode<int> g(17);
	TreeNode<int> h(1);
	TreeNode<int> i(4);
	TreeNode<int> j(6);
	TreeNode<int> k(8);
	TreeNode<int> l(11);
	TreeNode<int> n(12);

	a.left = &b;
	a.right = &c;
	b.left = &d;
	b.right = &e;
	c.left = &f;
	c.right = &g;
	d.left = &h;
	d.right = &i;
	e.left = &j;
	e.right = &k;
	f.left = &l;
	l.right = &n;

	printf("%d\n", isBST(&a, NULL, NULL));

}

이진 탐색 트리의 조건

1. 왼쪽에 있는 노드들이 자신보다 작아야 한다.

2. 오른쪽에 있는 노드들이 자신보다 커야 한다.

3. 좌,우의 서브트리도 이진 탐색 트리여야 한다.

위 조건에 따라 최소값과 최대값을 넘겨주며 재귀호출한다.
(왼쪽에 있는 서브트리를 탐색할때는 최대값으로 자기 자신을 주고, 오른쪽에 있는 서브트리를 탐색할때는 최소값으로 자기 자신을 준다.)