leetcode5-98. Validate Binary Search Tree

1. problem

1. given a list, check if it’s valid BST(left<node.val<right)

2. init

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> bool:

3. thought

1. 221220: recursive - no, need argument to valid, root val with left/right val, and return true/false.
2. 221221: recursive ok!
   1. inOrder walk from smallest to biggest.
   2. val bigger list[-1], and add it into list
   3. val less list[-1], reutrn False
   4. return Left AND Right result.

4. trouble

still need global variable.

5.final solution

class Solution:
    # 1. inOrder walk from smallest to biggest.
    # 2. val bigger list[-1], and add it into list
    # 3. val less list[-1], reutrn False
    # 4. return Left AND Right result.
    _list = []
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self._list = []
        return self.inOrder(root)
    def inOrder(self, root: Optional[TreeNode]) -> bool:
        if root is None: return False
        _L, _R = True, True
        if root.left: _L = self.inOrder(root.left)

        if len(self._list) == 0: 
            self._list.append(root.val)
        elif root.val > self._list[-1]: 
            self._list.append(root.val)
        else: 
            return False

        if root.right: _R = self.inOrder(root.right)
        return _L & _R

expert:

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    return self.inOrder(root, None, None)
def inOrder(self, root: Optional[TreeNode], minNode: Optional[TreeNode], maxNode: Optional[TreeNode]) -> bool:
    if root is None: return True
    if minNode and minNode.val >= root.val: return False
    if maxNode and maxNode.val <= root.val: return False
    return self.inOrder(root.left, minNode, root) & self.inOrder(root.right, root, maxNode)