湖北恩施论坛,栖霞牟氏庄园,热压机价格
题目来源：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
我要评论输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
思路：中序遍历
根据题意，二叉搜索树有如下的性质：
从上面的性质可以看出，二叉搜索树【中序遍历】得到的值一定是升序的。那么就这个特性，我们在中序遍历的时候就可以考虑检查当前节点的值是否大于前一个中序遍历到的节点的值。如果都大于则说明这个序列是升序的，那么就与前面就性质所得出的结论是吻合的，那么整棵树就是二叉搜索树。
关于【中序遍历】，它是二叉树遍历的一种。在二叉树中，中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。
具体实现代码如下。
# definition for a binary tree node.
# class treenode:
# def __init__(self, x):
# self.val = x
# self.left = none
# self.right = none
class solution:
def isvalidbst(self, root: treenode) -> bool:
stack = []
# -inf 表负无穷
inorder = float('-inf')
while root or stack:
# 将左点压入栈中
while root:
stack.append(root)
root = root.left
# 进行中序遍历
root = stack.pop()
# 如果当前节点的值小于前面中序遍历的值时，就不是二叉搜索树
while root.val <= inorder:
return false
# 更新中序遍历的值
inorder = root.val
root = root.right
return true
以上就是根据二叉搜索树的性质，用栈实现中序遍历的思路，进而解决《98. 验证二叉搜索树》问题的主要内容。
欢迎关注微信公众号《书所集录》
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
新手学习Python2和Python3中print不同的用法
Python基于os.environ从windows获取环境变量
网友评论