leetcode - Validate Binary Search Tree

leetcode - Validate Binary Search Tree

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.

  
  OJ's Binary Tree Serialization:

  The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

  Here's an example:
  

     1
    / \
   2   3
      /
     4
      \
       5
  

  The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

  /**
   * Definition for binary tree
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  struct TreeNode
  {
  	int val;
  	TreeNode *left;
  	TreeNode *right;
  	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
  #if 1 //第一種方法
  class Solution {
  public:
      bool isValidBST(TreeNode *root) {
  		return CheckBST(root,INT_MIN,INT_MAX);
      }
  private:
  	bool CheckBST(TreeNode *root,int min,int max)
  	{
  		if(root == NULL) return true;
  		return min < root->val && root->val < max && CheckBST(root->left,min,root->val) && CheckBST(root->right,root->val,max);
  	}
  };
  #endif // 1
  
  #if 0  //第二種方法
  class Solution {
  public:
      bool isValidBST(TreeNode *root) {
  		dfs(root);
  		for(int i = 1; i < result.size(); i++)
  		{
  			if(result[i-1] >= result[i]) return false;
  		}
  		return true;
      }
  private:
  	std::vector result;
  	void dfs(TreeNode *root)
  	{
  		if(root != NULL)
  		{
  			dfs(root->left);
  			result.push_back(root->val);
  			dfs(root->right);
  		}
  	}
  };
  #endif // 1