98. 验证二叉搜索树

My Solution

利用二叉搜索树的中序遍历一定是有序的解决

  1. class Solution {
  2.     List<Integer> list = new ArrayList<>();
  3.     public boolean isValidBST(TreeNode root) {
  4.         visit(root);
  6.         if (list.size() <= 1) {
  7.             return true;
  8.         }
  10.         for (int i = 1; i < list.size(); i++) {
  11.             if (list.get(i - 1) >= list.get(i)) 
  12.                 return false;
  13.         }
  15.         return true;
  16.     }
  18.     public void visit(TreeNode root) {
  19.         if (root == null) 
  20.             return ;
  22.         visit(root.left);
  23.         list.add(root.val);
  24.         visit(root.right);
  25.     } 
  26. }

递归写法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean isValidBST(TreeNode root) {
  18.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  19.     }
  21.     public boolean isValidBST(TreeNode root, long lower, long upper) {
  22.         if (root == null) {
  23.             return true;
  24.         }
  26.         if (root.val >= upper || root.val <= lower) {
  27.             return false;
  28.         }
  30.         return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
  31.     }
  32. }