Leetcode 098 Validate Binary Search Tree（递归）

本文主要是介绍Leetcode 098 Validate Binary Search Tree（递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Leetcode 098 Validate Binary Search Tree

解题思路：每个结点要维护当前子树结点中的最小值，和最大值。然后如果左结点不为空，递归判定左子树，并且左子树中的最大值不能大于当前值。右子树同理，但是最小值不能小于当前值。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {public:bool validBST(TreeNode* root, int& minVal, int& maxVal) {minVal = maxVal = root->val;int tmpMinVal, tmpMaxVal;if (root->left != NULL) {bool left =  validBST(root->left, tmpMinVal, tmpMaxVal);if (left == false || tmpMaxVal >= root->val)return false;minVal = min(minVal, tmpMinVal);}if (root->right != NULL) {bool right = validBST(root->right, tmpMinVal, tmpMaxVal);if (right == false || tmpMinVal <= root->val)return false;maxVal = max(maxVal, tmpMaxVal);}return true;}bool isValidBST(TreeNode* root) {if (root == NULL) return true;int minVal, maxVal;return validBST(root, minVal, maxVal);}
};

这篇关于Leetcode 098 Validate Binary Search Tree（递归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---