本文最后更新于 732 天前，其中的信息可能已经有所发展或是发生改变。
1.要点
- 搞清楚搜索二叉树和中序遍历的关系
- 看看甜姨的递归（直接用答题的函数，一直往上
return）
2.题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
3.示例
- 示例 1:
输入:
2
/
1 3
输出: true- 示例 2:
输入:
5
/
1 4
/
3 6
输出: false- 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。
4.甜姨的代码
代码语言：javascript复制class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 访问左子树
if (!isValidBST(root.left)) {
return false;
}
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
}5.自己的代码
代码语言：javascript复制 public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class TreeNode1 {
Integer val;
TreeNode1 left;
TreeNode1 right;
TreeNode1 parent;
Boolean isLeftChild;
TreeNode1(int val,TreeNode1 parent,Boolean isLeftChild) {
this.val = val;
this.parent=parent;
this.isLeftChild=isLeftChild;
}
}
public boolean isValidBST(TreeNode root) {
if(null == root){
return true;
}
Stack<TreeNode> nodeStack = new Stack<>();
Stack<TreeNode1> nodeStack1 = new Stack<>();
nodeStack.push(root);
nodeStack1.push(new TreeNode1(root.val,null,null));
while (!nodeStack.isEmpty()){
TreeNode node = nodeStack.pop();
TreeNode1 node1 = nodeStack1.pop();
if(!isSearchTree(node1,node1.val)){
return false;
}
if (node.right!=null){
nodeStack.push(node.right);
node1.right=new TreeNode1(node.right.val,node1,false);
nodeStack1.push(node1.right);
}
if(node.left!=null){
nodeStack.push(node.left);
node1.left=new TreeNode1(node.left.val,node1,true);
nodeStack1.push(node1.left);
}
}
return true;
}
public boolean isSearchTree(TreeNode1 node,int val){
if(null== node.parent){
return true;
}
if (node.isLeftChild){
if(val<node.parent.val){
return isSearchTree(node.parent,val);
}
}else{
if(val>node.parent.val){
return isSearchTree(node.parent,val);
}
}
return false;
}Post Views: 315
