力扣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移动到右节点重复上述操作直到currNone到达右子树最右节点中序遍历完成代码示例# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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 i0: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 可能存在last0有值 #但会被识别为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