SHARE
TWEET

Untitled

bbescos Feb 14th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.    
  13.     // This type of solution works when root->left <= root->val <= root->right
  14.     // This solution does not work when root->left < root->val < root->right
  15.     // It will fail if some nodes have as value 2^16 or -2^16
  16.     /*
  17.     bool isBST(TreeNode* root, int min, int max) {
  18.        
  19.         if (!root)
  20.             return true;
  21.        
  22.         bool isCurrent = root->val > min && root->val < max;
  23.         bool leftIsBST = isBST(root->left, min, root->val);
  24.         bool rightIsBST = isBST(root->right, root->val, max);
  25.        
  26.         return isCurrent && leftIsBST && rightIsBST;
  27.     }
  28.    
  29.  
  30.     bool isValidBST(TreeNode* root) {
  31.        
  32.         return isBST(root, numeric_limits<int>::min(), numeric_limits<int>::max());
  33.        
  34.     }
  35.     */
  36.    
  37.     // This type of solution works when root->left <= root->val <= root->right
  38.     // This solution works too when root->left < root->val < root->right
  39.    
  40.     bool isBST(TreeNode* root, TreeNode* left = nullptr, TreeNode* right = nullptr) {
  41.        
  42.         if (!root)
  43.             return true;
  44.        
  45.         if (left && left->val >= root->val)
  46.             return false;
  47.        
  48.         if (right && right->val <= root->val)
  49.             return false;
  50.        
  51.         return isBST(root->left, left, root) && isBST(root->right, root, right);
  52.     }
  53.  
  54.     bool isValidBST(TreeNode* root) {
  55.        
  56.         return isBST(root);
  57.        
  58.     }
  59.    
  60.     /*
  61.     vector<int> inOrderTraversal(TreeNode* root) {
  62.        
  63.         vector<int> answer;
  64.        
  65.         if (!root)
  66.             return answer;
  67.        
  68.         vector<int> left = inOrderTraversal(root->left);
  69.         answer.insert(answer.end(), left.begin(), left.end());
  70.         answer.push_back(root->val);
  71.         vector<int> right = inOrderTraversal(root->right);
  72.         answer.insert(answer.end(), right.begin(), right.end());
  73.        
  74.         return answer;
  75.     }
  76.    
  77.     // Do in-order traversal and check if the resulting array is sorted
  78.     // This type of solution works when root->left <= root->val <= root->right
  79.     // This solution works too when root->left < root->val < root->right
  80.     bool isValidBST(TreeNode* root) {
  81.        
  82.         vector<int> answer = inOrderTraversal(root);
  83.        
  84.         for (int i = 1; i < answer.size(); ++i) {
  85.             if (answer[i] <= answer[i-1])
  86.                 return false;
  87.         }
  88.        
  89.         return true;
  90.     }
  91.     */
  92.    
  93.    
  94. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top