首页 > 其他分享 >力扣 98. 验证二叉搜索树

力扣 98. 验证二叉搜索树

时间:2022-12-05 01:56:01浏览次数:62  
标签:right TreeNode val 二叉 力扣 98 root 节点 left

98. 验证二叉搜索树

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

递归

第一反应是,通过遍历判断当前节点和左右子树是否满足左节点<当前节点<右节点。如果仅通过遍历判断当前节点和左右子树是否满足,不能解决右子树中存在小于当前节点的值的问题。违反了节点的右子树只包含大于当前节点的数的要求。为了解决这个问题,在遍历的时候,参数除了当前节点外,还要给出上界和下界,通过上下界与当前节点的值的比较来判断到当前节点为止,递归路径是否满足题目要求。

对当前节点的判断:

  • 当前节点为空,返回true,为空说明此条递归路径已经走完了叶子节点,都没有出现问题,则当前路径是满足条件的。
  • 不为空,则判断当前节点与上下界是否满足条件;
    • 满足,分别进入左右子树,同时上下界更新。
    • 不满足,返回false

注意,题目中的节点值已经到了INT_MAXINT_MIN,所以初始上下界为LONG_MIN,LONG_MAX

查看代码
 /**
 * 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 work(TreeNode* cur,long long low,long long high){
        if(cur==nullptr)//到叶子节点都没有报错,则当前路径是满足有效的
            return true;
        if(cur->val>low&&cur->val<high)//cur节点是否满足
            return work(cur->left,low,cur->val)&&work(cur->right,cur->val,high);//分别进入子树
        else
            return false;//不满足
    }
    bool isValidBST(TreeNode* root) {
        return work(root,LONG_MIN,LONG_MAX);
    }
};

中序遍历

中序遍历按照左 -> 中 -> 右的顺序,中序遍历二叉搜索树,然后判断是否满足元素是升序排列。

查看代码
 /**
 * 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) {
        // if(root==nullptr)
        //     return true;
        stack<TreeNode*> sta;
        long long lastValue= (long long)INT_MIN - 1;
        while(!sta.empty()||root!=nullptr){
            while(root!=nullptr){//中序遍历:依次放入左节点,stack先进后出,会依次push出叶子左节点(左)和根节点(中)
                sta.push(root);
                root=root->left;
            }
            root=sta.top();//
            sta.pop();
            if(root->val<=lastValue)//不满足升序,无效
                return false;
            lastValue=root->val;//更新
            root=root->right;//可能为Null,(右)
        }
        return true;
    }
};

MORRIS

使用Morris中序遍历进行判断,介绍可以查看Morris遍历 介绍+前中后序遍历,但是注意但是必须跑完遍历代码,不能像上面一样发现不一致直接return false,因为Morris为了实现空间O(1)修改了二叉树的结构,如果不跑完遍历让其恢复修改,在反序列化时会报错。如这里。因为跑完了遍历,所以用时比前面两个方法久。

查看代码
 /**
 * 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) {
        long long lastValue=LONG_MIN;
        bool isValid=true;
        while (root != NULL)
        {
            if (root->left == NULL)
            {
                // cout << root->val << " ";//输出当前节点
                if(root->val<=lastValue)//不满足升序,无效
                {
                    isValid=false;
                }
                lastValue=root->val;//更新
                root = root->right;
            }
            else
            {
                // 找当前节点的前趋结点
                TreeNode* predecessor = root->left;
                while (predecessor->right != NULL
                    && predecessor->right != root)
                {
                    predecessor = predecessor->right;
                }

                // 使当前节点成为inorder的前序节点的右侧子节点
                if (predecessor->right == NULL)
                {
                    predecessor->right = root;
                    root = root->left;
                }
                //复原之前的修改
                else
                {
                    predecessor->right = NULL;
                    // cout << root->val << " ";//输出当前节点
                    if(root->val<=lastValue)//不满足升序,无效
                    isValid=false;
                    lastValue=root->val;//更新
                    root = root->right;
                }
            }
        }
        return isValid;
    }
};
 

标签:right,TreeNode,val,二叉,力扣,98,root,节点,left
From: https://www.cnblogs.com/fudanxi/p/16951100.html

相关文章

  • leetcode 101. 对称二叉树 js实现
    给你一个二叉树的根节点 root ,检查它是否轴对称。示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:false 提示:树......
  • CISAW风险管理学习笔记(6)-信息安全风险评估标准 GB/T20984
    个人学习总结,CISAW学习笔记之信息安全风险评估标准GB/T20984:......
  • 力扣 leetcode 209. 长度最小的子数组
    问题描述给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组[numsl,numsl+1,...,numsr-1,numsr],并返......
  • 求二叉树中最大的二叉搜索子树的头节点
    求二叉树中最大的二叉搜索子树的头节点作者:Grey原文地址:博客园:求二叉树中最大的二叉搜索子树的头节点CSDN:求二叉树中最大的二叉搜索子树的头节点题目描述给定一棵二......
  • 力扣18 四数之和
    题目:给你一个由n个整数组成的数组 nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],nums[b],nums[c],nums[d]] (若两个四......
  • 力扣 leetcode 547. 省份数量
    问题描述有n个城市,其中一些彼此相连,另一些没有相连。如果城市a与城市b直接相连,且城市b与城市c直接相连,那么城市a与城市c间接相连。省份是一组直接或间接......
  • 力扣 leetcode 200. 岛屿数量
    问题描述给你一个由'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此......
  • 力扣刷题01
    704.二分查找给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:num......
  • 【LeeCode】94. 二叉树的中序遍历
    【题目描述】给定一个二叉树的根节点 ​​root​​ ,返回 它的 中序 遍历 。​​​https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?favori......
  • 【LeeCode】104. 二叉树的最大深度
    【题目描述】给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。​​https://leetcode.cn/p......