[leetcode]98. Validate Binary Search Tree验证二叉搜索树
2024-10-15 10:29:47
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:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
Solution1: DFS
根据BST的性质: 左子树<根<右子树
要特别留心,对于input的root,没有办法给定一个确定的范围。所以初始化为null
5 (min, max) 5 :in(min,max)?
/ \ / / return true \ \ return false
1 4 1 update(min, 5), in (min, 5)? 4 update(5, 4), in (5,4)?
code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
/*why using null, null? 因为对于root,没有办法确定范围*/
return helper(root, null, null);
}
/* 因为上面定义的是null,这里initialize就应该是Integer而不是int*/
private boolean helper(TreeNode root, Integer min, Integer max) {
// base case
if (root == null)return true; // based on BST attribute
if ((min != null && root.val <= min) || (max != null && root.val >= max))
return false; // dfs
Boolean left = helper(root.left, min, root.val);
Boolean right = helper(root.right, root.val, max);
return left && right;
}
}
复杂度
Time: O(n) : visit each node
Space: O(h): h is the deepest height of such tree
最新文章
- 作业七:团队项目——Alpha版本冲刺阶段002
- jQuery 的原型关系图,整体把握jQuery
- Windows_cmd_命令
- IE6/IE7下:inline-block解决方案
- android内嵌入webview导致闪退
- Tomcat类加载器
- 重复T次的LIS的dp Codeforces Round #323 (Div. 2) D
- 解决JSON.stringify()自动将中文转译成unicode的方法
- 谈谈MySQL优化原理
- Android之Error: &#39;L&#39; is not a valid file-based resource name character解决办法
- winform中的dateTimePicker控件设置默认值为空
- 从理论到实践 全面理解HTTP/2
- exe4j中";this executable was created with an evaluation version exe4j";的解决
- 【Python全栈-后端开发】Django入门基础
- Linux指令之netstat
- Ubuntu 16.04 LTS network DIASBLED解决办法
- 27-java String 之间比较的幺蛾子
- Daily Scrum 12.22
- WAMP的一些配置修改
- Android 解压zip文件