• API
• FAQ
• Tools
• Archive
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.
64.
65.         if (!root)
67.
68.         vector<int> left = inOrderTraversal(root->left);
71.         vector<int> right = inOrderTraversal(root->right);
73.
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.
83.
84.         for (int i = 1; i < answer.size(); ++i) {
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.
Not a member of Pastebin yet?