valid binary search tree

gistfile1.txt

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


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
 /*
solution 1. 전체 노드를 순회하면서 tree를 streamlizing하여 extra 자료구조에 저장, 일일히 크기 비교(ex: {1,2,#,#,3} )
-> 가장 쉬운답, 인터뷰어가 원하는 답 아닌 것 같음

solution 2. 언제 invalid한가-> left branch: 자손의 값이 조상의 값보다 클때, 
right branch: 자손의 값이 조상의 값보다 작을때->
binarysearch tree의 특성을 생각해보자-> left로 갈수록 값이 '작아지고' right로 갈수록 값이 커짐 
-> left, right branch를 recursive로 순회하면서 현재까지의 최대값, 최소값을 저장, 
left의 경우 current max보다 갈수록 작아야하고, right는 current min보다 갈수록 커야함.

Time Complexity: O(n)

*/

class Solution {
    public:
    int min;
    int max;
    
    bool isValidBST(TreeNode *root) {
        min = INT_MIN;
        max = INT_MAX;
        
        return isValidNode(root);
    }
    
    bool isValidNode(TreeNode* node) {
        bool left, right;
        int temp = max;
        
        if(node == NULL) return true;
        
        if(node->val >= max || node->val <= min ) return false;
        
        max = node->val;
        left = isValidNode(node->left);
        
        max = temp;
        min = node->val;
        right = isValidNode(node->right);
        
        return left && right;
    }
};