leetcode:98. 验证二叉搜索树

98. 验证二叉搜索树

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/validate-binary-search-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在$[1,10^4]$ 内
• $-2^{31}$ <= Node.val <= $2^{31}-1$

解法

• 中序遍历+排序比较：二叉搜索树的中序遍历是有序序列，可以先进行中序遍历，然后再判断中序遍历序列是否有序的，且没有重复元素；
• 中序遍历递归过程中进行判断： 中序遍历的时候可以基于左子树的元素都要小于根节点这一性质进行判断，右子树的节点都要大于根节点；这里可以定义一个prev节点作为比较，然后递归进行中序遍历；

代码实现

中序遍历+排序后比较

python实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = []

        if not root:
            return True

        def helper(node):
            if not node:
                return node
            
            helper(node.left)
            res.append(node.val)
            helper(node.right)

        helper(root)   
        return res == sorted(res) and len(set(res)) == len(res)

c++实现

/** * 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 {
    
private:
    vector<int> res;
public:
    TreeNode* helper(TreeNode* node) {
    
        if (node == nullptr)
            return node;
        
        helper(node->left);
        res.push_back(node->val);
        helper(node->right);
        return node;
    }

    bool isValidBST(TreeNode* root) {
    
        helper(root);
        vector<int> res_copy = res;
        sort(res.begin(), res.end());
        set<int> s;
        for (int v: res_copy) {
    
            s.insert(v);
        }
        return res_copy == res && res_copy.size() == s.size();
    }
};

复杂度分析

• 时间复杂度： $O(NlogN)$ 排序需要的时间
• 空间复杂度： $O(N)$

中序遍历

python实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def __init__(self):
        self.prev = None

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        if not self.isValidBST(root.left):
            return False
        
        if self.prev and self.prev.val >= root.val:  # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            return False
        
        self.prev = root

        return self.isValidBST(root.right)

c++实现

/** * 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 {
    
private:
    TreeNode* prev = nullptr;

public:
    bool isValidBST(TreeNode* root) {
    
        if (root == nullptr)
            return true;
        
        if (not isValidBST(root->left))
            return false;
        
        if (prev != nullptr && prev->val >= root->val)  // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            return false;
        
        prev = root;

        return isValidBST(root->right);
    }
};

复杂度分析

• 时间复杂度： $O(N)$
• 空间复杂度： $O(N)$

参考

• https://www.geeksforgeeks.org/how-to-convert-a-vector-to-set-in-c/