98. Validate Binary Search Tree
in Coding Interview on Medium, Tree, Binary Search Tree, Recursion
이진 트리의 루트가 주어지면 유효한 이진 검색 트리(BST)인지 확인
98. Validate Binary Search Tree
재귀호출을 이용한 유효성 검증
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// Binary Search Tree (BST)
// 이진 검색 트리 유효성 검사
public boolean isValidBST(TreeNode root) {
return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean checkBST(TreeNode node, long left, long right) {
if (node == null) return true;
// 루트노드는 왼쪽보다 크고 오른쪽보다 작아야 한다.
if (!(left < node.val && node.val < right)) return false;
// Both the left and right subtrees must also be binary search trees.
// 오른쪽 자식이 노드보다 커야 할 뿐만 아니라 오른쪽 하위 트리의 모든 요소가 커야 합니다.
return checkBST(node.left, left, node.val) && checkBST(node.right, node.val, right);
}
}
중위순회를 이용한 유효성 검증
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// Binary Search Tree (BST)
// 이진 검색 트리 유효성 검사
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
// 중위순회: Left -> Root -> Right
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 이전노드 값이 더 크면 유효하지 않다.
if (pre != null && root.val <= pre.val) return false;
pre = root;
// 중위순회: Left -> Root -> Right
root = root.right;
}
return true;
}
}