首页 > 代码库 > [LeetCode] Validate Binary Search Tree （两种解法）
[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.
这是easy题么＝_= 被虐得好惨，开始想得简单，不就是验证BST咩，递归的话只用判断左右孩子是不是BST就行了。。。这就错了，孩子是BST并不能保证整颗树就是BST啊。比如下图
5
/ \
3 6
/ \ / \
1 8 4 7
5的左右孩子都分别是合法的BST，但是整颗树却不是，因为6的左孩子比5小；3的右孩子比5大。
所以在递归检测的时候，不仅仅要保证当前的树是BST，也要保证当前的树不破坏原有的BST结构，怎么办呢？
认真思考BST的结构性质会发现，BST就好像把一串数字做了很多切分，一部分放左变一部分放右边，一直这样递归的切下去。而这个切法可不是乱切，他是永远保持 “小的放左边，大的放右边” 的，这样切就有个性质，就是被切出来的每一段区域，都有严格的上下界。
3
/ \
1 5
/ \ / \
0 2 4 6
上图是一颗合法的BST，如果我们将其按照中序遍历方式展开可得：0 1 2 3 4 5 6
注意观察1，3，5 把序列切分成了4个区域，每个区域有一个数子分别是0，2，4，6。除了0没有下界，6没有上界以外，2和4都有明确的上下界。
所以在递归检测当中，我们应该同时传递上下界信息。
思路：在递归检测左右孩子的同时传递上下界信息，在递归调过程中更新上下界信息。
举个栗子：以上图为例，以根节点启动算法时，上下界信息为空，在检测1，3，5这个结构是否为合法BST后，递归的检测根节点为1的树（左孩子）并传入上界信息3；同样，递归检测根节点为5的树（右孩子）并传入下界信息3...
在递归过程中更新上下界信息，比如在检测到2这个节点的时候，更新了下界为1，而上界不用更新还是3。
bool validIter(TreeNode *node, TreeNode *left, TreeNode *right) { if (!node) return true; bool validLeft = true; bool validRight = true; if (node->left) { validLeft = (node->val > node->left->val); if (left) { validLeft = validLeft && (node->left->val > left->val); } } if (node->right) { validRight = (node->val < node->right->val); if (right) { validRight = validRight && (node->right->val < right->val); } } if (validLeft && validRight) { return validIter(node->left, left, node) && validIter(node->right, node, right); } return false;}bool isValidBST(TreeNode *root) { return validIter(root, NULL, NULL);}
要点：检测当前树是否为BST的时候还要检测是否违反了上下界的约束。
解法二：使用中序便利
上面的递归解法不太好想，我跌跌撞撞的提交了两次才对算法有了较深的理解。前面也说到，BST按照中序便利的话将会产生一个有序的序列，这是BST的性质。那为何不利用这个性质：先中序遍历产生数组，然后检查数组是否有序和是否有重复。
这个思路就是这么简单。。。中序遍历然后检查数组，所以才是easy题啊 （逃
void midOrderTraversal(TreeNode *node, vector<int> &s) { if (!node) return; midOrderTraversal(node->left, s); s.push_back(node->val); midOrderTraversal(node->right, s);}bool isValidBST(TreeNode *root) { if (!root) return true; vector<int> s; midOrderTraversal(root, s); for (int i = 1; i < s.size(); i++) { if (s[i] < s[i-1] || s[i] == s[i-1]) { return false; } } return true;}
[LeetCode] Validate Binary Search Tree （两种解法）