[Leetcode] Validate Binary Search Tree

Many tree questions can be addressed using recursive (helper) functions. To keep the variation for specific variables along the recursion, set the variables as parameters of the recursive function.

Description

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.

Examples

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.

Solution

bst: root > all elms in left & root < all elms in right

keep “last” to compare with current root -> Last means the last tranversed node in different level of recursion. Keep last in a global container. Use inorder traversal. Whenever traverse a node, the inorder shall guarantees last < curr, otherwise not a bst.

shift comparing border -> Give max and min border for each node to check if min < root < max. Use root as border. Root becomes max when going left, and min when right.

• code

ref: https://blog.csdn.net/fuxuemingzhu/article/details/70209865