Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1
이진 검색 트리 노드를 줄테니 Binary Search Tree가 맞는지 아닌지 검증하라 가 문제다.
BST 트리는 부모 노드 기준 왼쪽 자식 노드는 작아야 하고 오른쪽 자식 노드는 커야 한다. 이 법칙은 트리가 아래로 갈수록 계속 적용된다.
첫번째 트리 2,1,3 은 true이고, 두번째 트리는 leaf Node에 3 떄문에 false다. 3은 rootNode인 5보다 커야 한다.(우측에 있으니까)
이런 트리 특성에 맞추어 min, max 값을 계속 다른 값을 할당해 줌으로써 문제를 풀어야 한다.
난 이 문제를 못풀었던 이유가 1.루트 트리를 기준으로 좌/우 측 을 나눠 왼쪽 영역은 max가 rootNode보다 작도록 고정, 오른쪽 영역은 min = rootNode로 할당한후 전체 트리가 다 적용되도록 잘못 생각했다 -> 모든 노드마다 min or max값이 바뀐다. 왼쪽 자식 노드로 가면 max 값을 부모 노드 값으로, 오른쪽 자식 노드로 가면 min값을 부모노드 값으로 할당해야 한다.
정답 코드는 아래와 같다
const root = new Node(
5,
new Node(4, null, null),
new Node(6, new Node(3, null, null), new Node(7, null, null))
);
// console.log(root.left);
function isValidBST(root) {
if (!root) {
return true;
}
return dfsForValidBST(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
}
/**핵심 포인트 : 트리에서 좌측으로 내려가면 최대값이 변하고, 우측으로 내려가면 최소값이 변한다. */
function dfsForValidBST(node, min, max) {
// base case for recursion. return false if current node does not adhere to min and max
if (node.val <= min || node.val >= max) {
return false;
}
//left 자식 노드가 있다면, dfs(node.left)로 자식노드를 넣어주고,
//트리에서 왼쪽으로 내려 가면 최대값이 변해야 하므로, 현 node.val을 max param에 넣어줘 최대값을 부모노드 값으로 변화시킨다.
if (node.left) {
const isLeftValidBST = dfsForValidBST(node.left, min, node.val);
if (!isLeftValidBST) {
return false;
}
}
//right 자식 노드가 있다면, dfs(node.right)로 자식노드를 넣어주고,
//트리에서 오른쪽으로 내려 가면 최소값이 변해야 하므로, 현 node.val을 min param에 넣어줘 최소값을 부모노드 값으로 변화시킨다.
if (node.right) {
const isRightValidBST = dfsForValidBST(node.right, node.val, max);
if (!isRightValidBST) {
return false;
}
}
return true;
}
console.log(isValidBST(root));