首页 > 代码库 > 【LeetCode】98. Validate Binary Search Tree -判断是否为二叉排序树
【LeetCode】98. Validate Binary Search Tree -判断是否为二叉排序树
一、描述:
二、思路:
二叉排序树(BST),中序遍历的结果一定是非递减序列(来自百度百科);
本题中对于BST的定义是要么大于,要么小与,即遍历结果只能是递增序列,故可以通过判断中序遍历的结果序列是否是递增序列,来判断是否为合法BST;
另一种方法是使用递归;
三、代码:
1、非递归,通过中序遍历结果判断:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private List<Integer> list = new ArrayList<Integer>(); public boolean isValidBST(TreeNode root) { inorderTraversal(root); int size = list.size(); if(size==0 || size==1){ return true; } for(int i=0;i<size-1;i++){ if((list.get(i)) >= (list.get(i+1))){ return false; } } return true; } //中序遍历 public void inorderTraversal(TreeNode root){ if(root==null){ return; }else{ inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); } } }
2、递归:明天再写
【LeetCode】98. Validate Binary Search Tree -判断是否为二叉排序树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。