现在的位置: 首页 > 综合 > 正文

Validate Binary Search Tree_Leetcode

2018年03月18日 ⁄ 综合 ⁄ 共 698字 ⁄ 字号 评论关闭

一开始以为是题目SB,只是简单比较了父节点和子节点的值。结果发现原来是自己SB了,除了考虑父节点,还要考虑祖先节点的值,所以要用两个参数来记录每个节点valid的范围(根据父节点的值来不断调整)。

public class Solution {
	public boolean isValidBST(TreeNode root) {
		
		if(root == null)
			return true;
		
		return isValidBST(root, Long.MIN_VALUE,  Long.MAX_VALUE);
	}
	
	public boolean isValidBST(TreeNode node, long min, long max){
		
		
		if (node.left != null && (node.left.val >= node.val || node.left.val >= max || node.left.val <= min))
			return false;

		if (node.right != null && (node.right.val <= node.val || node.right.val <= min || node.right.val >=max))
			return false;
		
		if(node.left != null)
		{
			if(isValidBST(node.left, min, (max < node.val) ? max : node.val ) == false)
				return false;
		}
		
		
		if(node.right != null)
		{
			if(isValidBST(node.right, (min > node.val) ? min : node.val, max ) == false)
				return false;
		}
		
		return true;
		
	}
}

抱歉!评论已关闭.