LeetCode之验证二叉搜索树

问题描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入: 2 / \ 1 3

输出: true

示例 2:

输入: 5 / \ 1 4 / \ 3 6

输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。

问题解法

当中序遍历这种二叉树时应该得到的值是有序的。因此只需要在中序遍历的基础上保存当前的最大值max保证下一个值>max即可。如果这个值不大于max即为false。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private static int max=Integer.MIN_VALUE; public static boolean isValidBST(TreeNode root) { if(root==null) return true; if(root.left!=null) { boolean flag1=isValidBST(root.left); if(flag1==false) return false; } if(root.val>max) max=root.val; else return false; if(root.right!=null) { boolean flag2=isValidBST(root.right); if(flag2==false) return false; } return true; } }

问题

跑数据时，当根节点=0时力扣说我的输出错误但是我自己跑就没问题。

问题解决

因为输入为-2147483648时，答案就会相反。所以采用long的最小值表示。long max = Long.MIN_VALUE;

官方解法

其实中序遍历这种已经十分ok了。

简便

long max = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root==null) return true; if(!isValidBST(root.left)) return false; if(root.val<=max) return false; max=root.val; return isValidBST(root.right); }

第二种解法

思想相同只不过保存的是节点而不是值

class Solution { //用于判断当前节点的左节点 TreeNode pre=null; public boolean isValidBST(TreeNode root) { if(root==null) return true; if(!isValidBST(root.left)) return false; //这里用于判断是不是找到最左边的节点了，如果是就不用比较 if(pre==null) pre=root; //如果不是就比较这个节点和其左节点 else if(root.val<=pre.val) return false; pre=root; return isValidBST(root.right); } }