美文网首页面试准备LeeCode题目笔记
2019-09-21 验证二叉搜索树

2019-09-21 验证二叉搜索树

作者: Antrn | 来源:发表于2019-09-28 11:08 被阅读0次

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

    假设一个二叉搜索树具有如下特征:

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

    输入:

        2
       / \
      1   3
    输出: true
    

    示例 2:

    输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    

    解释: 输入为: [5,1,4,null,null,3,6]。
    根节点的值为 5 ,但是其右子节点值为 4 。

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        // bool isValidBST(TreeNode* root) {
        //     if(!root) return true;
        //     if(root->left){
        //         if(root->left->val>=root->val){
        //             return false;
        //         }
        //     }
        //     if(root->right){
        //         if(root->right->val<=root->val){
        //             return false;
        //         }
        //     }
        //     return (isValidBST(root->left)&&isValidBST(root->right));
        // }
        
        bool isValidBST(TreeNode* root) {
            return isValidBST(root, LONG_MIN, LONG_MAX);
        }
        bool isValidBST(TreeNode* root, long mn, long mx) {
            if (!root) return true;
            if (root->val <= mn || root->val >= mx) return false;
            return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
        }
    };
    

    相关文章

      网友评论

        本文标题:2019-09-21 验证二叉搜索树

        本文链接:https://www.haomeiwen.com/subject/vuiyuctx.html