[알고리즘] #Validate Binary Search Tree

출처 : https://leetcode.com/problems/validate-binary-search-tree/

Validate Binary Search Tree - LeetCode

문제 해석

주어진 이진 트리가 유효한 이진 탐색 트리 (BST)인지 확인하십시오.

BST는 다음과 같이 정의됩니다:

- 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드 만 포함됩니다.

- 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드 만 포함됩니다.

- 왼쪽 및 오른쪽 하위 트리는 모두 이진 탐색 트리 여야합니다.

 

 

 

 

 

 

---

#1. Recursion을 이용한 풀이

이 문제를 풀 때 주의할 점은, 단순히 자식 노드와 부모노드의 값만 비교하면 되는게 아니라 부모노드와 자식의 하위 노드들의 key 값과 비교를 해야한다는 것이다.

부모노드와 자식의 하위노드와도 비교해야하는 이유

그리고 반복되는 부분을 찾아보면,

(왼쪽 자식노드와 왼쪽자식노드에 올 수 있는 최소/최댓값 비교)

(오른쪽 자식노드와 오른쪽 자식노드에 올 수 있는 최소/최댓값 비교)

이다.

 

class Solution {
  public boolean isBSTHelper(TreeNode node, Integer lower_limit, Integer upper_limit) {
    if ((lower_limit != null) && (node.val <= lower_limit))
      return false;
    if ((upper_limit != null) && (upper_limit <= node.val))
      return false;

    boolean left = node.left != null ? isBSTHelper(node.left, lower_limit, node.val) : true;
    if (left) {
      boolean right = node.right != null ? isBSTHelper(node.right, node.val, upper_limit) : true;
      return right;
    } else
      return false;
  }

  public boolean isValidBST(TreeNode root) {
    if (root == null)
      return true;

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

 

위 알고리즘에 대해 차근차근 예제에 대입해보면 아래와 같다.