题目分析

合法的二叉搜索树，这个题目非常简单，并不是想为难大家，只是希望小伙伴们能够用不同的方法解决此题。

递归

最简单的方法是进行中序遍历，用一个容器接收数据，然后看这个容器中的元素是否满足严格递增的关系。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> v;
        subQuestion(root, v);
        for (int i = 1; i < v.size(); i++) if (v[i] <= v[i - 1]) return false;
        return true;
    }

    void subQuestion(TreeNode* root, vector<int>& v) {
        if (root) {
            subQuestion(root->left, v);
            v.push_back(root->val);
            subQuestion(root->right, v);
        }
    }
};

优化递归

因为我们每次只要记录前一个数字即可，因此我们设定一个指针pre指向前一个节点。判断一个树是否为搜索树，就是根节点的左子树是搜索树，并且根节点的值大于pre指向的节点的值，再让pre指向根节点，最后判断右子树即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution {
public:
    TreeNode* pre = NULL;

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

迭代

中序遍历是可以通过迭代进行的，先访问左子树，在访问左子树之前将根节点加入容器，然后容器的尾部就是最左端的节点，取出该节点，访问其右子树，在访问右子树的过程中也是先访问其左子树。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<TreeNode*> v;
        TreeNode* cur = root, * pre = NULL;
        while (cur || !v.empty()) {
            while (cur) {
                v.push_back(cur);
                cur = cur->left;
            }
            cur = v.back();
            v.pop_back();
            if (pre && pre->val >= cur->val) return false;
            pre = cur;
            cur = cur->right;
        }
        return true;
    }
};

刷题总结

在几天前给小伙伴们介绍了二叉搜索树的第k大节点这个题目，和本题非常类似，希望小伙伴们可以学习不同的解法，在面试中也能给自己加分。