Saturday, January 12, 2013

[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.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
» Solve this problem

[解题思路]

对于每一个子树,限制它的最大,最小值,如果超过则返回false。
对于根节点,最大最小都不限制;
每一层节点,左子树限制最大值小于根,右子树最小值大于根;
但是比较有趣的是,在递归的过程中还得不断带入祖父节点的值。

或者,中序遍历该树,然后扫描一遍看是否递增。


[Code]
递归
红字部分是关键点。不把变量遗传下去的话,没法解决如下例子:
{10,5,15,#,#,6,20}


1:    bool isValidBST(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      return VerifyBST(root, false, false, 0,0);  
5:    }  
6:    bool VerifyBST(TreeNode* root, bool left, bool right, int lmax, int rmin)  
7:    {  
8:      if(root== NULL)  
9:        return true;  
10:      if(left && root->val >= lmax) return false;  
11:      if(right && root->val <=rmin) return false;  
12:      bool leftValid = VerifyBST(root->left, true, right, root->val, rmin);  
13:      bool rightValid = VerifyBST(root->right, left, true, lmax, root->val);  
14:      return leftValid&&rightValid;        
15:    }  


Updates:
换个看起来简洁的

1:       bool isValidBST(TreeNode *root) {  
2:            return IsValidBST(root, INT_MIN, INT_MAX);  
3:       }  
4:       bool IsValidBST(TreeNode* node, int MIN, int MAX)   
5:       {  
6:            if(node == NULL)  
7:                  return true;  
8:            if(node->val > MIN   
9:                      && node->val < MAX  
10:                      && IsValidBST(node->left,MIN,node->val)  
11:                      && IsValidBST(node->right,node->val,MAX))  
12:                 return true;  
13:            else   
14:                 return false;  
15:       }  

No comments: