判断是否是二叉搜索树

判断一棵二叉树是否为二叉搜索树，可以通过中序遍历得到一个递增的序列，然后判断该序列是否为递增序列即可。

具体实现可以使用递归或者迭代的方式进行中序遍历，同时记录上一个遍历到的节点的值，与当前节点的值进行比较。

代码示例（递归实现）：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long long pre = LONG_LONG_MIN; // 记录上一个遍历到的节点的值
        return inorder(root, pre);
    }

    bool inorder(TreeNode* root, long long& pre) {
        if (!root) return true;
        if (!inorder(root->left, pre)) return false;
        if (root->val <= pre) return false;
        pre = root->val;
        return inorder(root->right, pre);
    }
};

相关问题

pta中序遍历树并判断是否为二叉搜索树C语言

在 C 语言中，如果要在 PTA（Problem Translation Assignment，编程作业题面）环境中实现中序遍历一棵树，并判断其是否为二叉搜索树（Binary Search Tree，BST），首先我们需要定义一个结构体表示树节点，然后实现中序遍历函数以及用于验证 BST 的辅助函数。

以下是一个简单的示例：

#include <stdio.h>
#include <stdbool.h>

// 定义树节点结构体
typedef struct TreeNode {
    int val;      // 节点值
    struct TreeNode *left;   // 左孩子指针
    struct TreeNode *right;  // 右孩子指针
} TreeNode;

// 中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->val);  // 输出节点值
        inorderTraversal(root->right);
    }
}

// 判断是否为二叉搜索树辅助函数
bool isValidBST(TreeNode* root) {
    return isBSTHelper(root, INT_MIN, INT_MAX);
}

bool isBSTHelper(TreeNode* node, int minVal, int maxVal) {
    if (node == NULL)
        return true;
    
    if (node->val <= minVal || node->val > maxVal)
        return false;
        
    return isBSTHelper(node->right, node->val, maxVal) &&
           isBSTHelper(node->left, minVal, node->val);
}

// 主函数测试
int main() {
    // 创建并初始化一个示例二叉搜索树
    TreeNode* root = malloc(sizeof(TreeNode));
    root->val = 5;
    root->left = malloc(sizeof(TreeNode));
    root->left->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = malloc(sizeof(TreeNode));
    root->right->val = 7;
    root->right->left = malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = NULL;

    // 遍历并检查是否为BST
    inorderTraversal(root);
    puts("");
    if (isValidBST(root))
        printf("Yes, it's a Binary Search Tree.\n");
    else
        printf("No, it's not a Binary Search Tree.\n");

    // 清理内存
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

在这个例子中，`inorderTraversal` 函数会按照左-根-右的顺序遍历树，打印出每个节点的值。`isValidBST` 和 `isBSTHelper` 是递归的辅助函数，它们一起检查当前节点值是否符合二叉搜索树的性质。

PTA中序遍历树并判断是否为二叉搜索树C语言

在C语言中，为了在二叉搜索树（BST，Binary Search Tree）中使用前序遍历（Preorder Traversal），我们通常会先访问根节点，然后递归地对左子树和右子树进行同样的操作。对于中序遍历（Inorder Traversal），则先遍历左子树，再访问根节点，最后遍历右子树。这两个过程可以用来确定一棵树是否为二叉搜索树，因为按照BST的特性，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。

以下是一个简单的中序遍历函数，用于检查输入的数组是否表示一个有效的BST：

#include <stdio.h>

// 定义二叉搜索树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 中序遍历函数
int inOrderTraversal(int arr[], int start, int end, TreeNode** root) {
    if (root == NULL)
        return 0;

    // 如果当前节点有效，继续中序遍历它的左子树
    if (arr[start] <= (*root)->val)
        return inOrderTraversal(arr, start + 1, end, &(*root)->left);

    // 访问根节点并将指针移到下一个元素
    printf("%d ", arr[start]);
    start++;

    // 遍历右子树
    return inOrderTraversal(arr, start, end, &(*root)->right);
}

// 判断给定数组是否构成BST
int isBST(int arr[], int n) {
    TreeNode* root = NULL;
    return inOrderTraversal(arr, 0, n - 1, &root) != 0;
}

int main() {
    int arr[] = {5, 3, 6, 2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    if (isBST(arr, n))
        printf("Yes, the array represents a BST.\n");
    else
        printf("No, the array does not represent a BST.\n");

    return 0;
}