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)
}
​