Problem:
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.
Example 1:
|
1 2 3 |
2 / \ 1 3 |
Binary tree [2,1,3], return true.
Example 2:
|
1 2 3 |
1 / \ 2 3 |
Binary tree [1,2,3], return false.
Solution 1
Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.
Time complexity: O(n)
Space complexity: O(n)
Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.
C++/long
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, LLONG_MIN, LLONG_MAX); } private: bool isValidBST(TreeNode* root, long min_val, long max_val) { if (!root) return true; if (root->val <= min_val || root->val >= max_val) return false; return isValidBST(root->left, min_val, root->val) && isValidBST(root->right, root->val, max_val); } }; |
C++/nullable
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, nullptr, nullptr); } private: bool isValidBST(TreeNode* root, int* min_val, int* max_val) { if (!root) return true; if ((min_val && root->val <= *min_val) ||(max_val && root->val >= *max_val)) return false; return isValidBST(root->left, min_val, &root->val) && isValidBST(root->right, &root->val, max_val); } }; |
Java/nullable
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 1 ms class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, null, null); } private boolean isValidBST(TreeNode root, Integer min, Integer max) { if (root == null) return true; if ((min != null && root.val <= min) ||(max != null && root.val >= max)) return false; return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); } } |
Solution 2
Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: bool isValidBST(TreeNode* root) { prev_ = nullptr; return inOrder(root); } private: TreeNode* prev_; bool inOrder(TreeNode* root) { if (!root) return true; if (!inOrder(root->left)) return false; if (prev_ && root->val <= prev_->val) return false; prev_ = root; return inOrder(root->right); } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 1 ms class Solution { private TreeNode prev; public boolean isValidBST(TreeNode root) { prev = null; return inOrder(root); } private boolean inOrder(TreeNode root) { if (root == null) return true; if (!inOrder(root.left)) return false; if (prev != null && root.val <= prev.val) return false; prev = root; return inOrder(root.right); } } |
Related Problem
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment