LeetCode 098 Validate Binary Search Tree

LeetCode

<div>

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

Example 1:

<pre>Input: root = [2,1,3] Output: true </pre>

Example 2:

<pre>Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
• -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1

</div>

题目大意：

验证BST

算法思路：

N/A

注意事项：

1. 用min, max法

Python代码：

def isValidBST(self, root: TreeNode) -> bool:
	return self.dfs(root, float('-inf'), float('inf'))

def dfs(self, root, min_val, max_val):
	if not root:
		return True
	if min_val >= root.val or root.val >= max_val:
		return False
	return self.dfs(root.left, min_val, root.val) and \
		   self.dfs(root.right, root.val, max_val)   

Java代码：

// Recommended method: use min max and devide & conquer
public boolean isValidBST2(TreeNode root) {
	return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

// val can be Integer.Min so use long
public boolean isValid(TreeNode root, long min, long max) {
	if(root == null)
		return true;
	
	if(min >= root.val || max <= root.val)
		return false;
	
	return isValid(root.left, min, root.val) && 
			isValid(root.right, root.val, max);
}

// Method 2: use isVisited
TreeNode lastVisited = null;
public boolean isValidBST(TreeNode root){
	if(root==null)
		return true;
	
	if(!isValidBST(root.left))
		return false;
	
	if(lastVisited!=null && lastVisited.val>=root.val)
		return false;
	
	lastVisited = root;//in-order traversal
			
	if(!isValidBST(root.right))
		return false;
	
	return true;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)