首页 > 代码库 > CCI4.5/LintCode Validate Binary Search Tree
CCI4.5/LintCode Validate Binary Search Tree
Validate BST是指按中序遍历niorder后左<node<右；
第一种方法： 先按inoreder遍历， 再放进ArrayList里用循环看是不是从小到大排序；
注意： 设置成员变量list时，如果先new作ArrayList， 则在main函数里每次用都得new个新的class对象；
如果不想在main里每次都new， 则在判断valid的函数里再new作ArrayList， 这样就每次用这个函数时都会自己new了；
（因为list特性的add功能会被不停地加， 而不是自身清空再加， 所以每次对不同的新对象时要先new）
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */public class Solution { public List<Integer> list; public void inorder(TreeNode root){ if(root == null) return; inorder(root.left); list.add(root.val); inorder(root.right); } /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ public boolean isValidBST(TreeNode root) { list = new ArrayList<Integer>(); inorder(root); for(int i = 0; i < list.size()- 1; i++){ if(list.get(i) >= list.get(i+1)) return false; } return true; // write your code here } }
第二种方法： 用自身递归， 看node节点的范围是不是： 左<node<右， 再对接着的左节点及右节点作为node来判断， 以此进行下去；
注意： 一个参数的函数里用个有三个参数的函数来体现实质是使用有三个参数的函数， 另外再对这有三参数的函数定义；
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */public class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, null, null); // write your code here } public boolean isValidBST(TreeNode root, Integer min, Integer max){ if(root == null) return true; if((min != null && root.val <= min) || (max != null && root.val >= max)) return false; if(!isValidBST(root.left, min, root.val) || !isValidBST(root.right, root.val, max)) return false; return true; }}
CCI4.5/LintCode Validate Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。