[LC] 98. Validate Binary Search Tree

[seungriyou]

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

Approach

Idea 1 (리스트에 기록)

주어진 트리가 BST인지 확인하려면, 중위 순회(inorder traversal) 를 돌면서 그 값들을 리스트로 모으고, 그 리스트가 오름차순 정렬되어 있는지 확인하면 된다.

이때, 단순히 sorted 결과와 같은지 보는 것이 아니라, "오름차순"으로 정렬되어 있는지 확인하는 것이 포인트이다! 왜냐하면 노드에 같은 값이 여러 개 들어있는 경우가 있을 수 있기 때문이다. (첫 시도 때 sorted와 비교만 하고 실패 ㅠ)

Idea 2 (리스트에 기록 X) 💡

ref: https://leetcode.com/problems/validate-binary-search-tree/solutions/32178/clean-python-solution

중위 순회를 하는 것과 동시에, 값이 유효한 범위 내에 있는지 floor, ceil 파라미터로 검사하는 방법을 적용할 수도 있다.

처음 호출 시에는 floor=float("-inf"), ceil=float("inf")가 될 것이다.

이렇게 하면 따로 노드의 값을 기록하는 리스트를 가질 필요가 없다!! 이런 트리 + 재귀 문제에는 언제 익숙해질까...

Complexity

• Time: O(n) (모든 노드 한 번씩 방문)
• Space: O(n) (리스트 / stack)