2022

算法题-判定二叉搜索树

BST 的性质：

• 左子树所有结点值 < 根结点值

• 右子树所有结点值 > 根结点值

• 左右子树也分别是 BST

98. 验证二叉搜索树 - 力扣（LeetCode）

方法一：递归判断左子树元素都比当前元素小，右子树元素都比当前元素大

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        //递归的看要求左边都比当前的小，右边都比当前的大
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

方法二：中序遍历

判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。

这是因为：中序遍历的步骤是：对于每个结点，先访问其「左子树」，再访问该结点，最后访问其「右子树」；而一棵二叉搜索树左子树结点必小于该结点、右子树上的结点必大于该结点，因此中序遍历的结果为严格单调递增。

这个代码更加板，好写。

class Solution {
public:
    std::vector<int> v;
    void dfs(TreeNode* root) {
        if (root == nullptr)
            return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
    bool isValidBST(TreeNode* root) {
        dfs(root);
        for (int i = 0; i < v.size() - 1; i++) {
            if (v[i] >= v[i + 1])
                return false;
        }
        return true;
    }
};

两者本质上是等价的，只是角度不同：

• 区间判断是 自顶向下，维护允许范围

• 中序遍历是 自底向上，检查最终顺序是否正确

typedef struct {                    // MAX_SIZE 为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

// 维护区间法判断 BST
bool checkBST(SqBiTree &T, int i, int l, int r) {
    if(i >= T.ElemNum) return true;        // 超出数组范围
    if(T.SqBiTNode[i] == -1) return true;  // 空节点

    int val = T.SqBiTNode[i];
    if(val <= l || val >= r) return false; // 不符合 BST 范围

    // 递归检查左右子树
    return checkBST(T, 2*i + 1, l, val) &&   // 左子树
           checkBST(T, 2*i + 2, val, r);    // 右子树
}
checkBST(T, 0, INT_MIN, INT_MAX);


//2.检查中序遍历序列
int prevVal = INT_MIN;
bool checkInOrder(SqBiTree &T, int i) {
    if(i >= T.ElemNum) return true;       // 越界视为空树
    if(T.SqBiTNode[i] == -1) return true; // 空节点

    // 左子树
    if(!checkInOrder(T, 2*i + 1)) return false;

    // 当前节点必须大于前一个节点
    if(T.SqBiTNode[i] <= prevVal) return false;
    prevVal = T.SqBiTNode[i];

    // 右子树
    return checkInOrder(T, 2*i + 2);
}
checkInOrder(T, 0);

应用题

太久没写代码脑子简直钝化了，第一反应竟然是选择排序排十次

1.堆排序

2.开一个大小为10的数组

• 用一个长度为 10 的数组 A 保存最小的 10 个数，初始值为最大数。

• 遍历原数组 M：

  • 若当前元素 s<A[9]（当前数组中最大值），将其插入到 A 中合适位置（保持升序），丢弃原最大值。

• 最终数组 A保存最小 10 个数。