想开个网站卖衣服的怎么做,建设网站需要申请报告,网站怎么做直播,建设网站 关于竣工结算的期限给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下#xff1a; 节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 英文题目 Given the root… 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 英文题目 Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtreeof a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. 解题思路
画了一个四层的二叉树发现递归方法是左子树的最右节点应该比根节点小右子树的最左节点应该比根节点大基于此写的代码事实上只要想着所有点然后更新边界就可以不用重复遍历来递归了
AC代码
# 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:def judge(root):if root.left is None and root.right is None:return Trueif root is None:return Trueleft, right, leftflag, rightflag root.left, root.right, True, Trueif left is not None:while left.right is not None:left left.rightleftflag root.val left.val and judge(root.left)if right is not None:while right.left is not None:right right.leftrightflag root.val right.val and judge(root.right)return leftflag and rightflagreturn judge(root)官方题解
想到使用边界后面思路就一下子通了
class Solution:def isValidBST(self, root: TreeNode) - bool:stack, inorder [], float(-inf)while stack or root:while root:stack.append(root)root root.leftroot stack.pop()# 如果中序遍历得到的节点的值小于等于前一个 inorder说明不是二叉搜索树if root.val inorder:return Falseinorder root.valroot root.rightreturn True
