From 23f1060bc7869adf7410a670f855c2570a17445f Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Thu, 11 Aug 2022 11:11:05 +0430 Subject: update --- 98/main.py | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100755 98/main.py diff --git a/98/main.py b/98/main.py new file mode 100755 index 0000000..4cf245e --- /dev/null +++ b/98/main.py @@ -0,0 +1,68 @@ +#!/usr/bin/env python3 +# not mine + +from typing import Optional + +# 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: + """dog-slow""" + + def isValid(root, node_min, node_max): + if root is None: + return True + + if node_min is not None and root.val <= node_min: + return False + if node_max is not None and root.val >= node_max: + return False + + return isValid(root.left, node_min, root.val) and isValid( + root.right, root.val, node_max + ) + + return isValid(root, None, None) + + +def main(): + node11 = TreeNode(2) + node12 = TreeNode(1) + node13 = TreeNode(3) + node11.left = node12 + node11.right = node13 + + node21 = TreeNode(5) + node22 = TreeNode(1) + node23 = TreeNode(4) + node24 = TreeNode(3) + node25 = TreeNode(6) + node21.left = node22 + node21.right = node23 + node23.left = node24 + node23.right = node25 + + node31 = TreeNode(5) + node32 = TreeNode(4) + node33 = TreeNode(6) + node34 = TreeNode(3) + node35 = TreeNode(7) + node31.left = node32 + node31.right = node33 + node33.left = node34 + node33.right = node35 + + solution = Solution() + print(solution.isValidBST(node11)) + print(solution.isValidBST(node21)) + print(solution.isValidBST(node31)) + + +if __name__ == "__main__": + main() -- cgit v1.2.3