98. Validate Binary Search Tree ⭐
Medium
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:
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.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
我一開始的方法是依照 Inorder 的順序將數字存入陣列後，再進行檢查。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
arr := make([]int, 0)
var helper func(*TreeNode)
helper = func(root *TreeNode) {
if root == nil { return }
if root.Left != nil {
helper(root.Left)
}
arr = append(arr, root.Val)
if root.Right != nil {
helper(root.Right)
}
}
helper(root)
for i:=1; i<len(arr); i++ {
if arr[i] <= arr[i-1] { return false }
}
return true
}
在討論區看到的漂亮方法：
對於每個左子樹而言， root 會比左子樹的值都大，若是有值大於 root 回傳 false ，右子樹也是相同概念。
func isValidBST(root *TreeNode) bool {
return tree(root, nil, nil)
}
func tree(root, min, max *TreeNode) bool {
if root == nil {
return true
}
if min != nil && root.Val <= min.Val {
return false
}
if max!= nil && root.Val >= max.Val {
return false
}
return tree(root.Left, min, root) && tree(root.Right, root, max)
}