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; } }