树的问题记得几个遍历.


98. 验证二叉搜索树

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  • 方法一:递归

从上往下递归比较方便
注意要使用Long类型进行极端值得判断

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return dfs(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
  4.     }
  6.     boolean dfs(TreeNode root,long  min,long max) {
  7.         if(root==null)
  8.             return true;
  9.         if(root.val>max || root.val<min)
  10.             return false;
  11.         // 记得 -1L  以及 +1L
  12.         return dfs(root.left,min,root.val - 1L) && dfs(root.right,root.val+1L,max);
  13.     }
  14. }
  • 方法二:中序遍历