分析

• 本题的考点：二叉搜索树。

• 存在两种方法。

方法1

• 递归遍历的过程中记录上一个节点的值，和当前节点的值比较，如果大于当前值则说明不是BST。

• 该方法使用C++实现。

• 这种做法和Leetcode 0897 递增顺序搜索树中提供的Java做法很类似。

方法2

• 先将中序遍历的结棍存储下来，然后判断是否存在逆序对即可。

• 该方法使用Java实现。

代码

• C++

class Solution {
public:
    TreeNode* pre = NULL;  // 中序遍历中当前遍历节点的前一个节点
    bool ans = true;

    bool isValidBST(TreeNode* root) {
        dfs(root);
        return ans;
    }

    void dfs(TreeNode *root) {

        if (!root) return;
        dfs(root->left);

        if (pre && pre->val >= root->val) {
            ans = false;
            return;
        }
        pre = root;

        dfs(root->right);
    }
};

• Java

class Solution {
    List<Integer> nums = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {

        dfs(root);

        for (int i = 1; i < nums.size(); i++)
            if (nums.get(i - 1) >= nums.get(i))
                return false;
        return true;
    }

    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        nums.add(root.val);
        dfs(root.right);
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为树中节点个数。

• 空间复杂度：C++做法 $O(h)$， Java做法 $O(n)$，h为树高。