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
» Solve this problem"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.[解题思路]
对于每一个子树,限制它的最大,最小值,如果超过则返回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:
Post a Comment