Validate Binary Search Tree
Medium
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.
Example 1:
2
/
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/
1 4
/
3 6
Input: [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.
题意
判断二叉搜索树是否valid
思路
【思路一】
中序遍历BST,递归函数返回一个对象(boolean isValid, int minVal, int maxVal)表示以root为根节点的子树是否valid,最小值和最大值
【思路二】
中序遍历BST,维护一个Integer表示上次访问的值,左/右子树不合法或pre < root.val则当前子树不合法
思路一和思路二的时间复杂度都是O(n),空间复杂度也都是O(n),其中n为BST的节点个数。但是思路二的时间常数更小。
代码
【思路一】
/*
* @lc app=leetcode id=98 lang=java
*
* [98] Validate Binary Search Tree
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Result {
boolean isValid;
int minVal, maxVal;
public Result(boolean isValid, int minVal, int maxVal) {
this.isValid = isValid;
this.minVal = minVal;
this.maxVal = maxVal;
}
}
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return checkValidBST(root).isValid;
}
private Result checkValidBST(TreeNode root) {
Result lres = null, rres = null;
int minVal, maxVal;
if (root.left != null) {
lres = checkValidBST(root.left);
if (!lres.isValid)
return new Result(false, 0, 0);
}
if (root.right != null) {
rres = checkValidBST(root.right);
if (!rres.isValid)
return new Result(false, 0, 0);
}
if (lres != null) {
if (lres.maxVal >= root.val) {
return new Result(false, 0, 0);
}
else {
minVal = lres.minVal;
}
}
else {
minVal = root.val;
}
if (rres != null) {
if (rres.minVal <= root.val) {
return new Result(false, 0, 0);
}
else {
maxVal = rres.maxVal;
}
}
else {
maxVal = root.val;
}
return new Result(true, minVal, maxVal);
}
}
【思路二】
/*
* @lc app=leetcode id=98 lang=java
*
* [98] Validate Binary Search Tree
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private Integer pre = null;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return inorderTraversal(root);
}
private boolean inorderTraversal(TreeNode root) {
if (root.left != null && !inorderTraversal(root.left)) {
return false;
}
if (this.pre != null && this.pre >= root.val) {
return false;
} else {
this.pre = root.val;
}
if (root.right != null && !inorderTraversal(root.right)) {
return false;
}
return true;
}
}