Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
Example 1:
Input:
2
/ 1 3
Output: true
Example 2:
5
/ 1 4
/ 3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node‘s value
is 5 but its right child‘s value is 4.
1 class Solution { 2 public: 3 bool minmax(TreeNode*root,pair<int,int>&ret) { 4 if (root->left == NULL && root->right == NULL) { 5 ret.first = root->val, ret.second = root->val; 6 return true; 7 } 8 int min=root->val, max=root->val; 9 if (root->left) { 10 if (minmax(root->left, ret) == false) 11 return false; 12 if (ret.second >= root->val) 13 return false; 14 min = ret.first; 15 } 16 if (root->right) { 17 if (minmax(root->right, ret) == false) 18 return false; 19 if (ret.first <= root->val) 20 return false; 21 max = ret.second; 22 } 23 ret.first = min, ret.second = max; 24 return true; 25 } 26 bool isValidBST(TreeNode* root) { 27 if (!root)return true; 28 pair<int, int>a; 29 return minmax(root,a); 30 } 31 };
19.3.2 [LeetCode 98] Validate Binary Search Tree
原文：https://www.cnblogs.com/yalphait/p/10460293.html
