LeetCode(98)Validate Binary Search Tree

제목은 다음과 같습니다.
분석은 다음과 같습니다.
이 제목이 귀속되지 않으면 하나의 특징을 이용하여 판단할 수 있다. 바로 중서가 나무를 훑어볼 때 얻은 node의 값은 반드시 점차적으로 증가하는 것이다.만약 귀속을 사용한다면, 제목이 정한 정의로 판단할 수 있다.
내 코드

//18ms
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        std::stack<TreeNode*> stack1;
        TreeNode* current = NULL;
        TreeNode* pre = NULL;
        while (root != NULL) {
            stack1.push(root);
            root = root->left;
        }
        while (!stack1.empty()) {
            current = stack1.top();
            stack1.pop();
            if ( pre!= NULL && pre->val >= current->val)
                return false;
            pre = current;  //NOTE: pre = current if() 。 current ， pre ， 。
            current = current->right;
            while(current != NULL) {
                stack1.push(current);
                current = current->left;
            }
        }
        return true;
    }
};

작은 매듭
(1) 반드시 정확하고 세심해야 한다. 처음부터 판단 조건을

if((pre!=NULL)&&(cur->val<=pre->val)) 

썼어요.

if((pre!=NULL)&&(cur->val<pre->val)) 

테스트를 통과하지 못했습니다.
(2) 귀속과 세 가지 반복은 나무 유형의 제목을 파악하는 기본적인 신기로 보인다.
update: 2014 - 11 - 28
차례차례 글을 썼다.틀린 것을 발견했는데 이 예는 통과되지 않았다.{10,5,15,#,#,6,20}
                         10
                 5                  15
                               6                20
생각해 보니 이렇게 고쳐서 노드마다min과max의 범위를 설정할 수 있습니다.
코드는 다음과 같습니다.
다음 코드는 결함이 있는 코드입니다.

class Solution {
public:
    bool myIsValidBST(TreeNode *root, int min_val, int max_val) {
        if (root == NULL) return true;
        else if (root->right != NULL && (root->right->val >= max_val || root->right->val <= root->val)) return false;
        else if (root->left != NULL && (root->left->val >= root->val || root->left->val <= min_val)) return false;
        else return myIsValidBST(root->left, min_val, root->val) && myIsValidBST(root->right, root->val, max_val);
    }
    bool isValidBST(TreeNode *root) {
        return myIsValidBST(root, INT_MIN, INT_MAX);
    }
};

이 코드는 보기에는 정확하지만 사실 노드value가 나타나는 것은 INT_와 같다민 또는 INT_MAX 때는 테스트를 통과할 수 없습니다.
다음과 같은 테스트 예:
{-2147483648,#,2147483647}
나는 리코드가 자신의 테스트 데이터를 업데이트했다고 의심하기 때문에 이 코드는 오래된 데이터에서 테스트할 수 있지만 새로운 데이터에서는 통과할 수 없다.
update: 2015-03-24 
통과할 수 있는 귀속 알고리즘은 매개 변수를 롱으로 바꾸면 된다는 것이다. 이렇게 하면 INT_민 - 1 및 민트_MAX + 1은 하계 및 상계를 나타냅니다(왼쪽에서 오른쪽 오프셋 구간의 상계 및 하계).

// 19ms
class Solution {
public:
    bool isValidBST_(TreeNode* root, long start, long end) {
        if (root == NULL) {
            return true;
        }
        if (root->val <= start) return false;
        if (root->val >= end) return false;
        if (root->left != NULL) {
            if (root->right != NULL) {
                return (root->val > root->left->val) && isValidBST_(root->left, start, root->val) 
                && (root->val < root->right->val) && isValidBST_(root->right, root->val, end);
            } else {
                return (root->val > root->left->val) && isValidBST_(root->left, start, root->val);
            }
        } else if (root->right != NULL) {
            return (root->val < root->right->val) && isValidBST_(root->right, root->val, end);
        } else {
            return true;    
        }
    }
    bool isValidBST(TreeNode *root) {
        return isValidBST_(root, (long)INT_MIN -1, (long)INT_MAX + 1);
    }
};

나중에 다시 보니 인터넷에서 더욱 간결한 방법은 다음과 같다.

class Solution {
public:
    bool isValidBST_(TreeNode* root, long start, long end) {
        if (root == NULL) {
            return true;
        }
        if (root->val <= start) return false;
        if (root->val >= end) return false;
        bool leftSubTree =  isValidBST_(root->left, start, root->val);
        bool rightSubTree = isValidBST_(root->right, root->val, end);
        return leftSubTree && rightSubTree;
    }
    bool isValidBST(TreeNode *root) {
        return isValidBST_(root, (long)INT_MIN -1, (long)INT_MAX + 1);
    }
};