Given the root of a binary tree, determine whether it is a valid binary search tree. A binary search tree requires that for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater.
Input
root: root of a binary tree (level-order, with null marking missing children)
Output
True if the tree is a valid BST; otherwise false.
Examples
Example 1
Inputroot = [1, 2, 3]
Outputfalse
Explanation: 2 is in the left subtree of 1 but is greater than 1.
Example 2
Inputroot = [1]
Outputtrue
Constraints
All node values are comparable integers.
A single node and an empty tree are valid.