首页 > 代码库 > [LeetCode] 98. Validate Binary Search Tree Java
[LeetCode] 98. Validate Binary Search Tree Java
题目：
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:
2 / 1 3
Binary tree [2,1,3], return true.
Example 2:
1 / 2 3
Binary tree [1,2,3], return false.
题意及分析：给出一课书，要求判断该树是不是二叉搜索树。二叉搜索树按照中序遍历得到的是一个升序序列，那么这道题只需要对树进行中序遍历即可，使用stack保存中间结果。这里需要注意的是理论最小值的获取，这里先获取最小值，然后当遍历到这个点时不需要做判断。
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null||(root.left==null&&root.right==null)) return true;
TreeNode minNode = root;
while(minNode.left!=null){
minNode=minNode.left;
}
long nowMax=minNode.val; //找到理论的最小值点
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
stack.add(node);
while(node.left!=null||!stack.isEmpty()){
if(node.left!=null){ //一直找到最左子节点
node = node.left;
stack.add(node);
}else{ //输出该点，对栈当前点的右节点做相同操作
TreeNode now = stack.pop();
if(now!=minNode){
if(now.val>nowMax){ //如果当前大于遍历的上一个那么当前最大值编程当前点最大值
nowMax = now.val;
}else{ //按照中序遍历输出，结果当前输出比上一个数小，那么直接返回false
return false;
}
}
if(now.right!=null) {
node = now.right;
stack.add(node); //将当前点加入stack中
}
}
}
return true;
}
}
[LeetCode] 98. Validate Binary Search Tree Java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。