출처 : leetcode BST 문제
이진 탐색 트리 (binary search tree) 는 이진 트리의 특별한 형태로 아래 조건과 같은 이진 검색 성질을 가진 트리이다.
- 각 노드의 값은 왼쪽에 저장된 모든 서브 트리 노드의 값보다 커야 한다.
- 각 노드의 값은 오른쪽에 저장된 모든 서브 트리 노드의 값보다 작아야 한다.
아래 그림은 이진 탐색 트리 (BST)의 예 이다
위 그림에서 볼 수 있듯이 루트노드 5의 경우를 보면 왼쪽에 위치한 모든 노드들 보다 큰값을 가지고 있다. 반대로 오른쪽에 위치한 모든 노드들 모다는 작은 값을 가진다.
Leetcode 강의 에서는 세가지 문제가 나왔다. Validate a BST, inorder traversal, inorder successor 각각의 문제를 풀어 보겠다.
Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
주어진 이진 트리가 BST 인지 증명하는 문제이다. 증명 방법은 위에 나온 것처럼 이진 검색 트리의 정의를 활용하면 된다. 현재 노드에서 왼쪽의 위치한 자식 노드가 가질수 있는 값은 무조건 현재 노드의 값보다 작아야 한다. 그리고 현재 노드에서 오른쪽에 위치한 노드는 무조건 현재 노드의 값보다는 커야 한다.
이 조건을 체크한 결과가 참이면 재귀적으로 현재 노드의 오른쪽 노드, 왼쪽 노드로 내려가서 다시 조건을 체크해가면 현재 트리가 BST인지를 확인 할 수 있다.
/*
struct node {
int val;
node* left;
node* right;
}
*/
bool isBST(node *root, long Min, long Max) {
//현재 노드가 NULL일 경우 반대편의 노드의 체크 결과로
//BST 여부를 결정하기 위아여 true를 리턴한다.
//1개의 노드로 만 구성된 트리의 경우는 무조건 BST가 됨.
if(root == NULL)
return true;
//현재 노드의 값이 부모 노드에서 전달된 값의 조건을
//만족 시키는 지 확인함. 현재 노드가 부모의 왼편에
//있었다면 Max에는 부모의 값이 전달되고.
//반대로 현재 노드가 부모의 오른쪽에 있었다면 Min에
//부모의 값이 전달 될것이다.
if(root->val < Min || root->val > Max) {
return false;
}
//왼쪽 노드에는 윗단계에서 받은 최소값을 최속값으로 현재
//노드의 값을 최대값으로 전달한다.
//오른쪽 노드에는 윗단계에서 받은 최대값을 최대값으로 현재
//노드의 값을 최소값으로 전달한다.
//왼쪽 노드, 오른쪽 노드 체크 결과가 모두 참이어야 true
//리턴하게 한다.
return (isBST(root->left,Min,root->val) &&
isBST(root->right,root->val,Max));
}
bool checkBST(node *root) {
return isBST(root, LONG_MIN, LONG_MAX);
}