[leetcode 75] 98. Validate Binary Search Tree

 

문제해석

이진트리의 root가 주어졌을 때 유효한 이진탐색트리인지 반환

유효한 이진탐색트리란?

• 노드의 왼쪽 서브트리는 반드시 노드의 키값보다 작아야 한다
• 노드의 오른쪽 서브트리는 반드시 노드의 키값보다 작아야 한다
• 왼쪽과 오른쪽 서브트리 모두 이진탐색트리여야 한다

 

정답 예 1) 이진트리 inorder순회시 값이 정렬되는 특성을 이용한 풀이

List<Integer> inorderVals = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
	// inorder로 순회해서 inorderVals에 값을 담으면
    // 정상적인 이진탐색트리의 경우 오름차순 정렬이 된다
    inorder(root);
    
    for (int i = 0; i < inorderVals.size() - 1; i++) {
    	// 오름차순 한 정렬 값 중 이전 값이 다음 값보다 큰 경우 유효하지 않다고 판단
        if (inorderVals.get(i) >= inorderVals.get(i+1)) {
            return false;
        }
    }
    
    // 모든 값이 오름차순으로 배열된게 검증 된 경우 유효
    return true;
}

public void inorder(TreeNode node) {
	// 노드가 없는 경우 종료
    if (node == null) {
        return;
    }
    // 노드의 왼쪽 서브트리 탐색
    inorder(node.left);
    // 노드의 값 저장
    inorderVals.add(node.val);
    // 노드의 오른쪽 서브트리 탐색
    inorder(node.right);
}

 

정답 예 2) 트리의 각 서브트리가 이진탐색트리의 조건을 만족하는지 검사  (가장 왼쪽노드가 가장 작은 값, 가장 오른쪽 노드가 가장 큰 값이어야 함)

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

    // 초기값에 대한 설정은 임의로 할 수 없어서 null을 넣어서 값이 할당됐을 경우만 체크
    return isValidSubTree(root, null, null);
}

public boolean isValidSubTree(TreeNode node, Integer min, Integer max) {
    // 노드가 없는 경우 종료
    if (node == null) {
        return true;
    }

    // 노드의 최소값은 현재 값보다 작아야하고, 노드의 최대값은 노드의 현재 값보다 커야한다.
    // 성립하지 않으면 유효하지 않음
    if (min != null && node.val <= min || max != null && node.val >= max) {
        return false;
    }

    //모든 서브트리에 대한 최소, 최대값 비교가 전부 true 유효, 한번이라도 유효하지 않으면 유요하지 않음
    return isValidSubTree(node.left, min, node.val) && isValidSubTree(node.right, node.val, max);
}