[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 = ; i < s.size(); i++) {
if (s[i] < s[i-] || s[i] == s[i-]) {
return false;
}
}
return true;
}
上一篇:【LeetCode】99. Recover Binary Search Tree


下一篇:【leetcode】Recover Binary Search Tree