(Leetcode) 98 - Validate Binary Search Tree

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice

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

내가 작성한 풀이

어떻게 해결할지 많은 고민을 하였다.

처음에는 그냥 단순히 부모와 자식간의 값의 비교하는 형태로 진행했었는데 그렇게 하면 테스트를 통과하지 못한다. 부모의 부모, 부모의 부모의 부모 … 까지 고려해야한다.

그래서 해당 노드의 위치가 정상적인 위치인지 어떻게 고려할 수 있을지 규칙을 찾아보니 left로 갈 때 max를 자신으로, right로 갈 때는 min을 자신으로 삼아가면서 dfs를 진행하면 해결할 수 있다는 것을 알게되었다.

class Solution {
	public boolean isValidBST(TreeNode root) {
		return dfs(root.left, (long) Integer.MIN_VALUE - 1, root.val)
			   && dfs(root.right, root.val, (long) Integer.MAX_VALUE + 1);
	}

	private boolean dfs(TreeNode node, long min, long max) {
		if (node == null) {
			return true;
		}

		// left로 갈 때 max를 자신으로, right로 갈 때는 min을 자신으로
		if (!(dfs(node.left, min, node.val)
			  && dfs(node.right, node.val, max))) {
			return false;
		}

		return node.val > min && node.val < max;
	}
}

특이한 점은 long을 사용했다는 점인데 문제에서 제시한 노드의 값 범위는 다음과 같다.

-2^31 <= Node.val <= 2^31 - 1

이 것은 정확하게 int의 범위와 일치하기 때문에 노드의 값이 Integer.MIN_VALUE, Integer.MAX_VALUE 일 경우 문제가 발생할 수 있는 여지가 있다. 그래서 어쩔 수 없이 long으로 받도록 처리하였다.

TC, SC

시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다. 트리가 균등한 형태라면 공간복잡도가 O(logn) 에 가까워진다.