设计算法,判定给定的二叉树是否是二叉排序树。设此二叉树以二叉链表作为存储结构。
时间: 2023-04-23 09:01:55 浏览: 283
写一算法,判断一棵二叉树是否是一棵二叉排序树。
可以通过中序遍历二叉树,判断遍历结果是否为升序序列来判断给定的二叉树是否是二叉排序树。具体步骤如下:
1. 对二叉树进行中序遍历,得到一个序列。
2. 判断序列是否为升序序列,如果是,则该二叉树是二叉排序树;否则,不是。
3. 中序遍历可以使用递归或者栈来实现。
4. 如果二叉树为空,则认为是二叉排序树。
代码示例(使用递归实现中序遍历):
bool isBST(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] <= nums[i - 1]) {
return false;
}
}
return true;
}
void inorder(TreeNode* root, vector<int>& nums) {
if (root == nullptr) {
return;
}
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
阅读全文