LeetCode 098 验证二叉搜索树

LeetCode 098 验证二叉搜索树

题目： 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

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

方法：中序遍历法 思路：中序遍历是先左子树再根节点再右子树，把一颗树经过中序遍历之后， 1.对它排序跟原来的进行比较，如果相同则是二叉搜索树 2.遍历数组，如果每一个数都小于后面的第一个数，则说明数组是递增的，符合二叉搜索树 代码：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static boolean isValidBST(TreeNode root) { List<TreeNode> list = new ArrayList<>(); if(root==null) return true; orderBST(root,list); for (int i = 0; i <list.size()-1 ; i++) { if (list.get(i).val >= list.get(i + 1).val) return false; } return true; } //中序遍历 public static void orderBST(TreeNode root,List<TreeNode> list){ if(root==null) return; orderBST(root.left,list); list.add(root); orderBST(root.right,list); }