验证二叉搜索树

解法一：通过中序遍历将整棵树装入vector，再判断数组是否单调

具体实现非常简单，但不是一个好方法，因为他需要先将所有节点的数值装入容器，再进行比较，然而实际上每次比较只需要使用到两个节点，这会造成空间的浪费

所以应该使用“边遍历，边比较”的方法

 1void traversal(TreeNode* root, std::vector<int>& v)
 2{
 3    if(!root) return;
 4
 5    traversal(root->left, v);
 6
 7    v.push_back(root->val);
 8
 9    traversal(root->right, v);
10}
11
12bool isValidBST(TreeNode* root)
13{
14    std::vector<int> vec;
15    traversal(root, vec);
16
17    int sz = vec.size();
18    for(int i = 0; i < sz - 1; i++)
19    {
20        if(vec[i+1] <= vec[i]) return false;
21    }
22    return true;
23}

解法二：使用指针成员装载当前节点的父节点，并在访问当前节点时就继续比较

这样就避免了在堆上分配内存，所有操作都只在栈上进行

相较于上一个方法，这个方法的空间复杂度从O(n)下降到了O(h),其中h为树的最大深度

 1class Solution
 2{
 3public:
 4    bool isValidBST(TreeNode* root)
 5    {
 6        if(!root) return true;                         // 遍历到叶子节点之后进行剪枝，返回上一个节点
 7        if(!isValidBST(root->left)) return false;      // 如果左子树底下的节点已经不满足规则，就没必要继续遍历了
 8        if(prev && root->val <= prev->val) return false;
 9        prev = root;
10        return isValidBST(root->right);                // 此时左边已经全部满足规则，只需要判断右子树是否也全部满足规则即可
11    }
12private :
13    TreeNode* prev = nullptr;
14};

补充解法：递归维护上下界

 1bool isValid(TreeNode* root, long min_val, long max_val)
 2{
 3    if(root == nullptr) return true;
 4    if(root->val <= min_val || max_val <= root->val) return false;
 5    return isValid(root->left, min_val, root->val) &&
 6           isValid(root->right, root->val, max_val);
 7}
 8bool isValidBST(TreeNode* root)
 9{
10    return isValid(root, LONG_MIN, LONG_MAX);
11}

来源：语雀原笔记