[leetcode]98. Validate Binary Search Tree

이 문제는, BST로 탐색이 가능한지를 판별하는 문제이다.
유효한 BST는 이렇게 정의가 된다.
1. 노드의 좌측 서브 트리에는 노드의 키보다 작은 키를 가진 노드만 있다.
2. 노드의 우측 서브 트리에는 노드의 키보다 큰 키를 가진 노드만 있다.
3. 좌 우측 서브 트리도 모두 이진 탐색 트리여야 한다.

트리의 순회는 재귀로 순회가 가능하다.
또한 BST 의 특성에 맞게, 하위값, 상한값의 개념이 들어간다.
만약 좌측으로 순회하게 될때는
하위값은 부모노드의 하한값.
상한값은 부모노드의 값이 된다.

우측 서브트리로 내려갈 때는,
하위값은 부모노드의 값,
상한값은 부모노드의 상한값이 된다.

1. dfs 순회를 하면서 이에 위배가 되는지를 확인하면 된다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    console.log(root)
};

우선 초기 root는 TreeNode 의 형태를 가지는 것을 확인할 수 있다.
따라서, node값, left, right의 값을 가져올 수 있다.

var isValidBST = function(root) {
  function dfs(node, low, high) {
    if (!node) return true;

    if ((low !== null && node.val <= low) || 
        (high !== null && node.val >= high)) {
      return false;
    }

    return dfs(node.left, low, node.val) &&
           dfs(node.right, node.val, high);
  }

  return dfs(root, null, null);
};

아까 언급한 원칙을 넣어서 dfs를 진행하면 된다.

2. 두번째로는 중위순회로 해결할 수 있다.

이진탐색 트리는 중위순회를 통해, 오름차순으로 모든 노드를 방문할 수 있다.
중위 순회 방식으로 좌측트리를 먼저 순회하고, 부모노드를 방문하고, 그 다음 우측 트리를 순회하기 때문이다.

따라서 중위순회가 오름차순으로 진행되지 않는다면, 이것은 유효한 이진트리가 아니다.

var isValidBST = function(root) {
  let prev = null;

  function inorder(node) {
    if (!node) return true;

    if (!inorder(node.left)) return false;

    if (prev !== null && node.val <= prev) return false;
    prev = node.val;

    return inorder(node.right);
  }

  return inorder(root);
};

둘다 성능은 O(N)이다.

좀 더 어려운 문제
94. Binary Tree Inorder Traversal
501. Find Mode in Binary Search Tree

참고자료
https://leetcode.com/problems/validate-binary-search-tree/
https://www.algodale.com/problems/validate-binary-search-tree/