力扣98.验证二叉搜索树
给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含严格小于当前节点的数。
- 节点的右子树只包含严格大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
几种思路：
1.中序遍历得到各个节点value的序列，验证是否严格递增（直观，但是慢，内存开销大）
2.dfs直接判断各个节点是否合法，否则直接返回
3.Morris遍历：利用空闲的叶子节点存储回溯值：
对于中序遍历，当我们遍历到curr节点时，需要先将左子树全部输出后才能输出curr和右子树，而左子树输出完成的标志恰好是curr的前驱完成了输出（curr左子树的最右节点）；
因此为了充分利用这一特性，我们在curr的前驱的右节点（原本为空）中存放curr的地址作为一个临时的节点（这一操作在第一次访问curr的时候完成），当我们再次访问到curr的前驱并且发现前驱右节点已经被标记时，证明curr的左子树已经完成了遍历；
于是通过这个临时节点返回curr并将这个前驱的右节点设置为None（断开连接 保持树的形状）；
输出curr，并把curr移动到右节点；
重复上述操作，直到curr=None（到达右子树最右节点，中序遍历完成）
代码示例：
# 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: #中序遍历得到严格递增序列 # result = [] # def dfs(root): # if not root:return None # dfs(root.left) # result.append(root.val) # dfs(root.right) # dfs(root) # for i in range(len(result)): # if i==0:continue # if result[i]<=result[i-1]:return False # return True #直接dfs检查各个节点 # def dfs(node, lower, upper): # # 空节点是合法的 # if not node: # return True # # 当前节点必须在 (lower, upper) 开区间内 # if node.val <= lower or node.val >= upper: # return False # # 左子树：所有值必须 < node.val # # 右子树：所有值必须 > node.val # return (dfs(node.left, lower, node.val) and # dfs(node.right, node.val, upper)) # # 初始范围：负无穷到正无穷 # return dfs(root, float('-inf'), float('inf')) #Morris中序遍历二叉树 result = True def morris(root): #从根节点开始，当指向null时结束 curr = root last = None nonlocal result while curr: if curr.left: pre = findrpre(curr,curr) if not pre.right:#当前前驱还未设置临时回溯节点 pre.right = curr #设置前驱 curr = curr.left else:#该前驱已经被标记，拆除临时节点，返回并输出原节点，开始遍历右子树 #result.append(curr.val) if last is not None and last>= curr.val: #return False result = False last = curr.val pre.right = None curr = curr.right else: # if last and 可能存在last=0（有值） #但会被识别为false，因此使用 isnotNonoe if last is not None and last>= curr.val: #return False result = False #result.append(curr.val) last = curr.val curr = curr.right #return True def findrpre(root,check):#找前驱 pre = root.left while pre.right and pre.right!=check: pre = pre.right return pre #左子树的最右节点 morris(root) return result