首页 > 代码库 > [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 (两种解法)