[LeetCode] 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.

解法1：min/max法

这是我觉得最直接了当、简洁易懂的方法：

1. 先top-down递归，由父节点来传递子节点的值所允许的范围minVal < x->val < maxVal。如果该条件不符合，返回false。

2. 如果上述条件符合，只说明当前节点x本身符合BST条件。还需要bottom-up递归来检查当前节点的左右子树是否也都符合BST条件。左子树的取值范围为(minVal, x->val)，右子树取值范围为(x->val, maxVal)。

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public: bool isValidBST(TreeNode *root) { return validateBST(root, INT_MIN, INT_MAX); } bool validateBST(TreeNode *root, int minVal, int maxVal) { if(!root) return true; if(root->val<=minVal || root->val>=maxVal) return false; return validateBST(root->left, minVal, root->val) && validateBST(root->right, root->val, maxVal); } };

解法2：inorder traversal法
1. 对一个BST进行inorder traverse，必然会得到一个严格单调递增序列，否则则是invalid BST。

2. Inorder traverse时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool isValidBST(TreeNode *root) { int curMax = INT_MIN; return validateBST(root, curMax); } bool validateBST(TreeNode *root, int &curMax) { if(!root) return true; if(!validateBST(root->left, curMax)) return false; if(curMax >= root->val) return false; curMax = root->val; return validateBST(root->right, curMax); } };

ln 10:检验左子树是否valid，并通过引用得到左子树的最大值curMax。

ln 11-12:在左子树valid的情况下，判断当前节点是否大于curMax。在当前节点也valid的情况下，更新curMax为当前节点。

ln 13:当左子树和当前节点都valid时，返回右子树的检验结果即可。