Validate Binary Search Tree
2021/7/31 6:06:31
本文主要是介绍Validate Binary Search Tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Code link: https://leetcode.com/problems/validate-binary-search-tree/
Constraint:
- The number of nodes in the tree is in the range [1, 104].
- -2^31 <= Node.val <= 2^31 - 1
Idea
For each node, we will need to check if its value is within certain range [min, max]. As we traverse downward, we have to update the range accordingly. Basically we need to update the upper bound when we go left and lower bound when we go right. Initially the range could be [-2^31 , 2^31 - 1]
- Attemp 1.
class Solution { public boolean isValidBST(TreeNode root) { return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValidBSTHelper(TreeNode root, int min, int max) { if (root == null) { return true; } if (root.val <= min || root.val >= max) { return false; } return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max); } }
This solution doesn't work for the case where a node contains the the value of (2^31 - 1) or (-2^31). For example given the case [2147483647], the output would be false where it should be true.
- Attemp 2 Recursive solution
A nice for BST is that if we inspect its values with in-order way, it is an ascending sequence. With that in mind, we can first do an in-order traversal and keep track of all the values in this order. Then we just need to verify whether the numbers are monotonously increasing or not.
class Solution { public boolean isValidBST(TreeNode root) { List<Integer> inOrderPath = new ArrayList<>(); isValidBSTHelper(root, inOrderPath); for (int i = 1; i < inOrderPath.size(); i++) { if (inOrderPath.get(i) <= inOrderPath.get(i - 1)) { return false; } } return true; } private void isValidBSTHelper(TreeNode root, List<Integer> inOrderPath) { if (root == null) { return; } isValidBSTHelper(root.left, inOrderPath); inOrderPath.add(root.val); isValidBSTHelper(root.right, inOrderPath); } }
-
Time: O(n) as in-order traversing and inspecting the list both take O(n).
-
Space: O(n). Both recursion stack and the list take O(n).
-
Attemp 3 Iterative solution:
class Solution { public boolean isValidBST(TreeNode root) { List<Integer> path = new ArrayList<>(); TreeNode cur = root; Stack<TreeNode> st = new Stack<>(); while (cur != null || !st.isEmpty()) { if (cur != null) { st.push(cur); cur = cur.left; } else { cur = st.pop(); path.add(cur.val); cur = cur.right; } } for (int i = 1; i < path.size(); i++) { if (path.get(i) <= path.get(i - 1)) { return false; } } return true; } }
- Time: O(n)
- Space: O(n) as both the stack and list has size up to n.
Potenailly we could check for number sequence while traversing the tree, instead of checking it in later run:
... if (path.size() > 0 && path.get(path.size() - 1) >= cur.val) { return false; } ...
这篇关于Validate Binary Search Tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享