请实现一个函数,打印给定二叉树的中序遍历序列并判定他是否是一棵二叉搜索树(Binary Search Tree)。
时间: 2023-06-15 08:06:06 浏览: 230
用c实现的二叉树的中序遍历的读取与存储,能体现出向左倒的二叉树的打印界面,界面简单.rar
二叉搜索树的定义是:左子树中所有节点的值小于根节点的值,右子树中所有节点的值大于根节点的值,且左右子树都是二叉搜索树。
中序遍历是按照左子树、根节点、右子树的顺序遍历二叉树,如果中序遍历序列是递增的,那么这棵二叉树就是一个二叉搜索树。
以下是Python的代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> List[int]:
"""
中序遍历二叉树,返回遍历序列
"""
res = []
if not root:
return res
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
def isValidBST(root: TreeNode) -> bool:
"""
判断给定的二叉树是否是二叉搜索树
"""
inorder = inorderTraversal(root)
for i in range(1, len(inorder)):
if inorder[i] <= inorder[i-1]:
return False
return True
```
首先我们定义了一个TreeNode类来表示二叉树的节点。然后我们定义了一个inorderTraversal函数来进行中序遍历,这里我们使用了迭代的方式来遍历二叉树,使用了一个栈来维护遍历的顺序,每次先将左子树的节点全部入栈,然后弹出栈顶节点,将其值加入结果序列,并将右子树的根节点入栈。最后返回遍历序列。
接着我们定义了一个isValidBST函数,这个函数先使用inorderTraversal函数得到给定二叉树的中序遍历序列,然后遍历序列,如果发现当前节点小于等于前一个节点,那么就不是一个二叉搜索树,返回False,否则遍历完整个序列后返回True。
注意,在实际工作中,二叉搜索树的实现可能会更加复杂,例如需要支持插入、删除等操作,需要考虑平衡等问题。
阅读全文