Contents

# 98. Validate Binary Search Tree

## 題目 :

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 :

Note

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

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.

#### 解題思路 :

• 這題考察的是你對於Binary Search Tree特性的掌握度
• 基本的特性我就不贅述了，這邊講一個大家比較會忽略掉的特性: 當BST進行inorder排序時，必然是由小到大的有序排列
• 換言之，我們也可以用此特性去檢查BST，若它的Inorder排序並非由小到大也就代表它不符合BST
• 以下提供兩個解法，一個是利用BST定義去完成的解法，另一個是利用inorder特性去完成的解法

### Recursive解法-1

• time complexity: O(n) , space complexity: O(1)

Runtime: 4 ms, faster than 95.20% of Go online submissions for Validate Binary Search Tree.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ import "math" func isValidBST(root *TreeNode) bool { if root == nil { return true } return isBST(root, math.MinInt64, math.MaxInt64) } func isBST(root *TreeNode, min int, max int) bool { if root == nil { return true } if min >= root.Val || max <= root.Val { return false } return isBST(root.Left, min, root.Val) && isBST(root.Right, root.Val, max) } ``````

### Recursive解法-2-利用Inorder特性

• time complexity: O(n) , space complexity: O(1)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func isValidBST(root *TreeNode) bool { var prev *TreeNode var travel func(node *TreeNode) bool travel = func(node *TreeNode) bool { if node == nil { return true } leftRes := travel(node.Left) if prev != nil && node.Val <= prev.Val { return false } prev = node rightRes := travel(node.Right) return leftRes && rightRes } return travel(root) } ``````