diff options
-rwxr-xr-x | 98/main.py | 68 |
1 files changed, 68 insertions, 0 deletions
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() |