leetcode || 98、Validate Binary Search Tree

problem:
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
confused what  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ.
Hide Tags
 
Tree Depth-first Search
제목: 두 갈래 나무가 두 갈래 나무를 검색하는지 판단하고 두 갈래 나무의 성질을 주의하십시오. 왼쪽 나무의 모든 노드는 아버지 노드보다 작고,
오른쪽 하위 트리의 모든 노드가 부모 노드보다 큽니다.
thinking:
(1) 검색 트리에 대한 정의 곡해를 반복적으로 쓰기 시작했다.왼쪽 아이와 오른쪽 아이만 비교했다.틀렸어.

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if(root==NULL)
            return true;
        TreeNode *parent = root;
        TreeNode *left_child=parent->left;
        TreeNode *right_child=parent->right;
        bool r=true;
        bool l=true; 
        if(left_child!=NULL)
        {
            if(left_child->val<parent->val)
                l=isValidBST(left_child);
            else
                l=false;
        }
        if(right_child!=NULL)
        {
            if(right_child->val>parent->val)
                r=isValidBST(right_child);
            else
                r=false;
        }
        return l&&r;      
    }
};

(2) 올바른 해법은 중순으로 훑어보는 것이다.DFS(비귀속법)에서 두 갈래 트리를 차례로 훑어보면 노드의 VAL은 증가 서열이어야 한다.
code:

class Solution {
  public:
      bool isValidBST(TreeNode *root)
      {
        vector<int> ret=inorderTraversal(root);
        int n=ret.size();
        if(n<2)
            return true;
        for(int i=1;i<n;i++)
        {
            if(ret[i]<=ret[i-1])
                return false;
        }
        return true;
      }
  protected:
      vector<int> inorderTraversal(TreeNode *root) {  
                 vector<int> ret;  
                 stack<TreeNode*> _stack;  
                 TreeNode *tmp=root;  
                 while(tmp!=NULL || !_stack.empty())  
                 {  
                     if(tmp!=NULL)  
                     {  
                         _stack.push(tmp);  
                         tmp=tmp->left;  
                     }  
                     else  
                     {  
                         tmp=_stack.top();  
                         _stack.pop();  
                         ret.push_back(tmp->val);  
                         tmp=tmp->right;  
                     }  
                 }  
               return ret;     
          }  
  };