leetcode98 Validate Binary Search Tree

  1 """
  2 Given a binary tree, determine if it is a valid binary search tree (BST).
  3 Assume a BST is defined as follows:
  4     The left subtree of a node contains only nodes with keys less than the node's key.
  5     The right subtree of a node contains only nodes with keys greater than the node's key.
  6     Both the left and right subtrees must also be binary search trees.
  7 Example 1:
  8     2
  9    / 
 10   1   3
 11 Input: [2,1,3]
 12 Output: true
 13 Example 2:
 14     5
 15    / 
 16   1   4
 17      / 
 18     3   6
 19 Input: [5,1,4,null,null,3,6]
 20 Output: false
 21 Explanation: The root node's value is 5 but its right child's value is 4.
 22 """
 23 """
 24 好题，提供四种解法,可与leetcode1305结合起来看https://www.cnblogs.com/yawenw/p/12284717.html
 25 解法一：自己AC 中序遍历(递归） + sorted() + set()
 26 思路是将二叉搜索树中序遍历存入nums
 27 先set()处理，将输入为[1, 1]的情况排除
 28 再sorted()与nums比较是否相等
 29 因为如果为二叉搜索树 nums应该是没有重复值并且递增的
 30 """
 31 class TreeNode:
 32     def __init__(self, x):
 33         self.val = x
 34         self.left = None
 35         self.right = None
 36 
 37 class Solution:
 38     def isValidBST(self, root: TreeNode) -> bool:
 39         if not root:
 40             return True  # bug input为[]时
 41         res = self._inorder(root, [])
 42         return res == sorted(set(res))  # bug 加上set是为了判断input[1,1]
 43 
 44     def _inorder(self, root, nums):
 45         if root.left:
 46             self._inorder(root.left, nums)
 47         nums.append(root.val)
 48         if root.right:
 49             self._inorder(root.right, nums)
 50         return nums
 51 """
 52 解法二：递归
 53 关键点在于初始化的时候
 54 用无穷大和无穷小作为根结点的上下值
 55 """
 56 class Solution2:
 57     def isValidBST(self, root):
 58 
 59         return self._isValidBST(root)
 60 
 61     def _isValidBST(self, root, low=float('-inf'), high=float('inf')): # ！！！关键的初始化
 62         if not root:
 63             return True
 64         value = root.val
 65         if not low < value < high:
 66             return False
 67         return self._isValidBST(root.left, low, value) and 
 68                self._isValidBST(root.right, value, high)
 69 """
 70 解法三：将解法一的递归中序遍历变为栈
 71 """
 72 class Solution3:
 73     def isValidBST(self, root):
 74         stack = []
 75         inorder = []
 76         if not root:
 77             return True
 78         while stack or root: #非递归中序遍历
 79             while root:
 80                 stack.append(root)
 81                 root = root.left
 82             root = stack.pop() #bug这里写了 x = stack.pop(),影响上面while循环
 83             inorder.append(root.val)
 84             root = root.right #bug 这里写成了stack.append(root.right),原因没理解
 85         return inorder == sorted(set(inorder))
 86 """
 87 解法四：将解法二的递归变为迭代(queue)
 88 """
 89 class Solution4:
 90     def isValidBST(self, root):
 91         if not root:
 92             return True
 93         queue = [(root, float('-inf'), float('inf'))]
 94         while queue:
 95             root, low, high = queue.pop(0)
 96             value = root.val
 97             if not low < value < high:
 98                 return False
 99             if root.left: #if判别不能少
100                 queue.append((root.left, low, value))
101             if root.right:
102                 queue.append((root.right, value, high))
103         return True