[LeetCode/98/Java]Validate Binary Search Tree

[LeetCode/98/Java]Validate Binary Search Tree

풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
    	return isValidBST(root, null, null);
    }
    
    boolean isValidBST(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
            return false;
        }
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

후기

요구사항

이진 트리의 루트가 주어지면 유효한 BST(이진 검색 트리)인지 확인합니다.
유효한 BST는 다음과 같이 정의됩니다.
1.노드의 왼쪽 하위 트리에는 노드 키보다 작은 키를 가진 노드만 포함됩니다.
2.노드의 오른쪽 하위 트리에는 노드 키보다 큰 키가 있는 노드만 포함됩니다.
3.왼쪽 및 오른쪽 하위 트리도 모두 이진 검색 트리여야 합니다.

 

위의 요구사항을 처음에 이해하는게 살짝 어려웠는데요

왼쪽 하위 트리에는 노드 키보다 작은 키를 가진 노드만 포함이라고 했는데

이것은 루트까지도 포함한다는 이야기입니다.

그러므로 루트를 기준으로 왼쪽으로는 작은값이 계속 들어가는지

오른쪽에는 루트보다 큰 값들이 들어가는지를 판단해야 합니다.

 

time complexity O(N)
space complexity O(N)