请实现一个函数,打印给定二叉树的中序遍历序列并判定他是否是一棵二叉搜索树(Binary Search Tree)。
时间: 2023-09-18 11:05:48 浏览: 159
### 回答1:
二叉搜索树(Binary Search Tree):是一棵空树或者具有下列性质的二叉树:若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;它的左右子树也分别为二叉搜索树。
中序遍历序列:对于任意一棵二叉树,中序遍历的结果都是一个序列,这个序列称为中序遍历序列。
因此,判断一棵二叉树是否为二叉搜索树,可以先进行中序遍历,再判断遍历结果是否为升序序列。
以下是 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
res.extend(inorderTraversal(root.left))
res.append(root.val)
res.extend(inorderTraversal(root.right))
return res
def isBST(root: TreeNode) -> bool:
res = inorderTraversal(root)
for i in range(1, len(res)):
if res[i] <= res[i-1]:
return False
return True
```
其中,`TreeNode` 是二叉树的节点类,`inorderTraversal` 函数是实现二叉树中序遍历的递归函数,`isBST` 函数是判断二叉树是否为二叉搜索树的函数。
### 回答2:
要实现这个函数,首先我们可以使用递归的方式对二叉树进行中序遍历,即先遍历左子树,再访问根节点,最后遍历右子树。遍历过程中将遍历到的节点值保存到一个数组中。
接下来,我们需要判断该数组是否是按升序排列的,即判断是否是一棵二叉搜索树。我们可以遍历数组,依次比较相邻的节点值,如果前一个节点的值大于等于后一个节点的值,则认为不是二叉搜索树。反之,如果整个数组都符合这个条件,则认为是一个二叉搜索树。
以下是一个简单的实现代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root):
if not root:
return []
result = []
inorder(root, result)
return result
def inorder(root, result):
if not root:
return
inorder(root.left, result)
result.append(root.val)
inorder(root.right, result)
def isBST(root):
inorder_result = inorderTraversal(root)
for i in range(1, len(inorder_result)):
if inorder_result[i] <= inorder_result[i-1]:
return False
return True
```
这个函数的时间复杂度是O(n),其中n是二叉树中节点的数量,因为我们需要遍历每个节点并将节点的值保存到数组中。
阅读全文