requirements

You are given the root node of a binary tree to determine whether it is a valid binary search tree.

The effective binary search tree is defined as follows:

The left subtree of a node contains only numbers less than the current node. The right subtree of a node only contains numbers greater than the current node. All left and right subtrees must themselves also be binary search trees.

Example 1:

Input: root = [2,1,3] output: trueCopy the code

Example 2:

Input: root = [5,1,4,null,null,3,6] output: false description: the root node is 5, but the right child node is 4.Copy the code

The core code

class TreeNode:
    def __init__(self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def isValidBST(self, root: TreeNode) - >bool:
        inorder = list()

        self.inorderTra(root,inorder)

        for i in range(len(inorder)-1) :if inorder[i] >= inorder[i+1] :return False
        return True

    def inorderTra(self,root,inorder) :
        if not root:
            return None
        
        self.inorderTra(root.left,inorder)
        inorder.append(root.val)
        self.inorderTra(root.right,inorder)

        return 
Copy the code

Their thinking: this topic use their thinking is in the sequence traversal, because we left subtree values are smaller than the root node, the value of the right subtree are bigger than the root node, so if it is a binary search tree in sequence traversal after get list is sorted, we only need to test the data is from childhood.