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