98. 验证二叉搜索树

image.png

递归解法一

  1. public class Solution {
  3.     // 存放中序遍历结果，二分搜索树中序遍历的结果是从小往大排序的
  4.     List<Integer> list = new ArrayList<>();
  6.     public boolean isValidBST(TreeNode root) {
  7.         if (root!= null) {
  8.             isValidBST(root.left);
  9.             list.add(root.val);
  10.             isValidBST(root.right);
  11.         }
  13.         // 注意要小于等于，搜索树里不能有相同元素
  14.         for (int i = 1; i < list.size(); i++) {
  15.             if (list.get(i - 1) >= list.get(i)) return false;
  16.         }
  17.         return true;
  18.     }
  19. }

递归解法二，代码结构更清晰

  1. class Solution {
  3.     private ArrayList<Integer> tempList = new ArrayList<>();
  5.     public boolean isValidBST(TreeNode root) {
  6.         preOrder(root);
  8.         for (int i = 1; i < tempList.size(); i++) {
  9.             if (tempList.get(i - 1) >= tempList.get(i)) return false;
  10.         }
  11.         return true;
  12.     }
  14.     public void preOrder(TreeNode node) {
  15.         if (node != null) {
  16.             preOrder(node.left);
  17.             tempList.add(node.val);
  18.             preOrder(node.right);
  19.         }
  20.     }
  21. }