首页 > 代码库 > Leetcode: Valide Binary Search Tree
Leetcode: Valide Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node‘s key.The right subtree of a node contains only nodes with keys greater than the node‘s key.Both the left and right subtrees must also be binary search trees.
思维难度：87，开始我以为只要每个子树都满足左子树根<根<右子树根，就可以保证BST了，太天真了，需要保证的是左子树所有节点都小于根，而并非仅仅左子树根。所以Recursion里面要存的是可以取值的范围。其实就是对于每个结点保存左右界，也就是保证结点满足它的左子树的每个结点比当前结点值小，右子树的每个结点比当前结点值大。对于根节点不用定位界，所以是无穷小到无穷大，接下来当我们往左边走时，上界就变成当前结点的值，下界不变，而往右边走时，下界则变成当前结点值，上界不变。如果在递归中遇到结点值超越了自己的上下界，则返回false，否则返回左右子树的结果。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public boolean isValidBST(TreeNode root) {12 return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);13 }14 15 public boolean isValid(TreeNode root, int min, int max) {16 if (root == null) return true;17 if (root.val<=min || root.val>=max) return false;18 return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);19 }20 }
网上另外一种做法是用中序遍历的方法遍历BST，BST的性质是遍历后数组是有序的。根据这一点我们只需要中序遍历这棵树，然后保存前驱结点，每次检测是否满足递增关系即可。注意以下代码我么用一个一个变量的数组去保存前驱结点，原因是java没有传引用的概念，如果传入一个变量，它是按值传递的，所以是一个备份的变量，改变它的值并不能影响它在函数外部的值，算是java中的一个小细节。
1 public boolean isValidBST(TreeNode root) { 2 ArrayList<Integer> pre = new ArrayList<Integer>(); 3 pre.add(null); 4 return helper(root, pre); 5 } 6 private boolean helper(TreeNode root, ArrayList<Integer> pre) 7 { 8 if(root == null) 9 return true;10 boolean left = helper(root.left,pre);11 if(pre.get(0)!=null && root.val<=pre.get(0))12 return false;13 pre.set(0,root.val);14 return left && helper(root.right,pre);15 }
Leetcode: Valide Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。