验证二叉搜索树 Posted on 2021-06-24 00:00:00 2021-06-26 00:00:00 by Author 摘要 给定一颗二叉树,能不能判断这颗二叉树是一颗二叉搜索树尼????? # 验证二叉搜索树 1. 题目描述 - 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: - 节点的左子树只包含小于当前节点的数。 - 节点的右子树只包含大于当前节点的数。 - 所有左子树和右子树自身必须也是二叉 2. 示例描述 - 示例一 ``` 输入: 2 / \ 1 3 输出: true ``` - 示例二 ``` 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。 ``` 3. 解题思路 - 了解过搜索二叉树的彦祖和亦菲都知道,一般牵扯搜索二叉树十次就有九次要使用中序遍历去解决问题。对于本题来说也是一样。 - 在解决本题之前,还是需要了解一下二叉搜索树的概念,这样才能更好的解决本题。 - 对于本题的解决方法有许多种,这里我使用了两种方法去解决这道题目,第一种就是中序遍历二叉树,把遍历的节点记录在一个集合中,为什么不记录在数组中,因为我们前提不知道二叉树有多少个节点,这就导致我们定义数组前就不能给数组分配内存大小。中序遍历完整棵二叉树,然后判断集合中元素是否从小到大排列的,如果整个集合中的元素有顺序排列,那么这颗二叉树就是一颗二叉搜索树,否则就不是。 - 第二种解法,就是在中序遍历过程中进行处理,一颗二叉树要满足 是一颗搜索二叉树,那么正在处理的节点的左子树下所有节点都小于该节点的值,该节点右子树下 的所有节点的值都大于该节点的值,同样除此节点外,所有其他的节点也满足该条件。所有我们在中序遍历的时候,只要在适当的位置加上该条件就可以了。下面将给出这两种解决方式的示例。 4. 代码示例 ```java 方法一: //定义一个遍历过程中中序遍历所走过的节点的值的集合 List<Integer> tempList = new ArrayList<>(); public boolean isValidBST(TreeNode root) { //中序遍历 midOrder(root); return isValidByList(tempList); } public void midOrder(TreeNode treeNode) { //中序遍历的一般形式 if (treeNode != null) { midOrder(treeNode.left); //记录中序遍历所经过节点的值 tempList.add(treeNode.val); midOrder(treeNode.right); } return; } //判断中序遍历后集合中的值排列顺序是否从小到达 public boolean isValidByList(List<Integer> list) { //如果二叉树是空树,那也是一颗搜索二叉树 if (list.size() == 0) return true; int temp = list.get(0); //判断集合中的值是否有序 //只要一个不满足条件,就不是一颗二叉搜索树 for (int i = 1; i < list.size(); i++) { if (temp < list.get(i)) { temp = list.get(i); } else return false; } return true; } ``` ```java 方法二: TreeNode temp = null; public boolean isValidBST(TreeNode root) { //如果正在遍历的节点为空,那么返回为true; if (root == null) return true; //判断该节点左子树是否是一颗二叉搜索树 boolean leftIsValid = isValidBST(root.left); //中序遍历回溯后,判断左子树节点是否大于等于父节点,如果是的话返回false if (temp != null && temp.val >= root.val) return false; //记录前一个节点 //因为是中序遍历,前一个节点就是该节点的字节点 temp = root; //继续判断右子树是否是一颗二叉搜索时 boolean rightIsValid = isValidBST(root.right); //如果左子树与右子树都是一颗二叉搜索树,那么该节点下所有的二叉树都是二叉搜索树 return leftIsValid && rightIsValid; } ```
{{ item.content }}
{{ child.content }}