[leetcode 98] Validate Binary Search Tree

root 노드를 중심으로 왼쪽 subtree는 전부 root 노드보다 값이 작아야 하고

오른쪽 subtree는 전부 root 노드보다 값이 커야 한다.

 

- subtree에 있는 모든 노드가 조건을 만족해야 한다.

- 같아도 안된다.

 

1) inorder를 이용한 방식-stack 사용

- stack을 사용하여 왼쪽 가장 아래 노드까지 내려간다.

- subtree기준으로 어쨌든 오른쪽 노드가 가장 크면 되기 때문에 값의 크기를 비교한 후엔 현재노드를 right 노드로 설정한다.

using namespace std;
class Solution {
public:
   
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*>s;
        long long inorder = -LONG_MAX;
        
        while(!s.empty() || root !=nullptr){
            while(root != nullptr){
                s.push(root);
                root = root->left;
            }
            TreeNode* top = s.top();
            s.pop();
            
            if(top -> val <=inorder) return false;
            inorder = top->val;
            root = top->right;
        }
        return true;
    }
};