Monday, November 10, 2014

[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时,返回右子树的检验结果即可。

3 comments:

  1. 第一种解法不能通过root 就是int_max 的 test case,branch left 过刚比较max, branch right 过就比较min可以过
    http://fisherlei.blogspot.com/2013/01/leetcode-validate-binary-search-tree.html

    ReplyDelete
  2. 第二种解法貌似不能通过 input 仅为 INT_MIN的情况
    要把 curMax 类型设为 long 并且初始化为 INT_MIN - 1

    ReplyDelete