98. 验证二叉搜索树

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

这道题的题干里面已经包含了解题的要素。只需要用递归的思路将题干中的语序调换一下即可。

• “节点的左子树只包含小于当前节点的数”：对树中的单个节点而言，如果他是父节点的左儿子，那么它的值比父节点的值要小；

• “节点的右子树只包含大于当前节点的数”：对树中的单个节点而言，如果他是父节点的右儿子，那么它的值比父节点的值要大。

用递归的方式遍历树中的各个节点，递归函数内检查节点的值是否满足区间 (left_father_val, right_father_val) 之内。区间的上下界是递归函数的参数。每次递归调用前更新区间上下界的值。递归调用的入口处上下界为 [-inf, inf] 。

另一种思路

用中序遍历得到二叉搜索树节点值的序列后，判断该序列是否是严格递增的。

复杂度分析

时间复杂度：O(N)
空间复杂度：二叉搜索树最坏情况下深度=节点数=递归栈深度，O(N)

知识点

二叉树，递归，中序遍历

代码

/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidSubTree(root, numeric_limits<long>::min(), numeric_limits<long>::max());
    }

    bool isValidSubTree(TreeNode* node, long lowerBound, long upperBound) {
        if (!node) {
            return true;
        }
        return ((lowerBound < node->val) && (node->val < upperBound))
            && isValidSubTree(node->left, lowerBound, node->val)
            && isValidSubTree(node->right, node->val, upperBound);
    }
};

Leetcode的数据中有一个刚好是2^32-1，所以这里用 long 来确保初始上下界为比二叉树内所有节点值都大/小。

参考资料

1. Leetcode官方题解