2020-09-12发表2023-09-12更新算法竞赛10 分钟读完 (大约1473个字)

左子树恒小于右子树的二叉搜索树

二叉搜索树（BST）是二叉树的一种特殊表示形式。二叉搜索树的性质要求每个节点的值必须大于其左子树中的任何节点的值，并且小于其右子树中的任何节点的值。节点的值不能等于其左子树中的节点值或右子树中的节点值。

二叉搜索树简介

二叉搜索树（Binary Search Tree，BST）是一种常见的数据结构，具有以下性质：

每个节点都有一个值，这个值必须大于其左侧子树中的任何节点的值。
同时，这个值必须小于其右侧子树中的任何节点的值。
左子树和右子树也都是二叉搜索树。

下面是一个二叉搜索树的例子：

这个性质使得二叉搜索树具有有序性质，因此可以高效地进行搜索、插入和删除操作。因为根据节点的值大小，我们可以快速确定在哪个子树中查找目标值，从而减少搜索的时间复杂度。

但需要注意的是，如果树不平衡，即某一侧子树的高度远大于另一侧子树，可能会导致树的性能下降，甚至可能退化为链表，此时操作的时间复杂度可能变为O(n)，其中n是树中的节点数。因此，通常情况下，我们会采取一些平衡二叉搜索树的数据结构，如AVL树或红黑树，来保持树的平衡性，以确保操作的高效性。

如果左子树等于右子树，即某个节点的左子树中的节点值与右子树中的节点值相等，这种情况会导致问题，因为在搜索、插入或删除节点时，无法唯一确定节点应该位于左子树还是右子树。这将导致树的性质被破坏，可能导致不一致的操作结果。因此，在设计和维护二叉搜索树时，确保每个节点的值都不等于其左子树或右子树中的节点值是非常重要的。只有在这种情况下，二叉搜索树的性质才能得以保持，以确保有效的搜索、插入和删除操作。

这篇文章之后，我们提供了一个习题来让你验证一个树是否是二叉搜索树。你可以运用我们上述提到的性质来判断。前一章介绍的递归思想也可能会对你解决这个问题有所帮助。

像普通的二叉树一样，我们可以按照前序、中序和后序来遍历一个二叉搜索树。但是值得注意的是，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。因此，中序遍历是二叉搜索树中最常用的遍历方法。

我们也添加了让你求解二叉搜索树的中序后继节点（in-order successor）的题目。显然，你可以通过中序遍历来找到二叉搜索树的中序后继节点。你也可以尝试运用二叉搜索树的特性，去寻求更好的解决方案。

验证二叉搜索树

在检查节点值时，只考虑了节点与其直接的左子节点和右子节点的关系，但没有考虑到节点与整个左子树或右子树的关系。这会导致一些情况被忽略。正确的做法是使用上界和下界来维护节点值的范围，即节点值应该介于左子树的最大值和右子树的最小值之间，而不仅仅是与直接子节点的比较。为了修正这些问题，需要使用递归方式，并传递上界和下界的信息。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
using gg=long long;

class Solution {
public:
    bool dfs(TreeNode *u,gg lower,gg upper) {
        if(!u) return true;
        if(u->val<=lower||u->val>=upper) {
            return false;
        }
        return dfs(u->left,lower,u->val) && dfs(u->right,u->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return dfs(root,LONG_MIN,LONG_MAX);
    }
};