98. 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.
• A single node tree is a BST

Example

Example 1:

Input:  {-1}
Output：true
Explanation：
For the following binary tree（only one node）:
	      -1
This is a binary search tree.

Example 2:

Input:  {2,1,4,#,#,3,5}
Output: true
For the following binary tree:
	  2
	 / \
	1   4
	   / \
	  3   5
This is a binary search tree.

Example 3:

Input: {5,1,4,#,#,3,6}
Output: false

For the following binary tree:

    5
   / \
  1   4
     / \
    3   6

Explanation: The root node's value is 5 but its right child's value is 4.

method: recursion

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} 
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
10.  * }; 
11.  */  
12. class Solution {  
13. public:  
14.     bool isValidBST(TreeNode* root) {  
15.         return helper(root, NULL, NULL);  
16.     }  
17.       
18.     bool helper(TreeNode* root, TreeNode* lower, TreeNode* upper) {  
19.         if (!root) return true;  
20.           
21.         if (lower && lower->val >= root->val) return false;  
22.         if (upper && upper->val <= root->val) return false;  
23.           
24.         if (!helper(root->right, root, upper)) return false;  
25.         if (!helper(root->left, lower, root)) return false;  
26.           
27.         return true;  
28.     }  
29. };  

method: iteration

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} 
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 
10.  * }; 
11.  */  
12. class Solution {  
13. public:  
14.     /** 
15.      * @param root: The root of binary tree. 
16.      * @return: True if the binary tree is BST, or false 
17.      */  
18.     bool isValidBST(TreeNode * root) {  
19.         // write your code here  
20.         if (!root) return true;  
21.         if (!root->left && !root->right) return true;  
22.           
23.         stack<TreeNode*> st;  
24.         TreeNode* node = NULL;  
25.           
26.         while (!st.empty() || root) {  
27.             while (root) {  
28.                 st.push(root);  
29.                 root = root->left;  
30.             }  
31.               
32.             root = st.top();  
33.             st.pop();  
34.               
35.             if (node && root->val <= node->val) return false;  
36.               
37.             node = root;  
38.             root = root->right;  
39.         }  
40.           
41.         return true;  
42.     }  
43. };