二叉树abcdefghij先序遍历_二叉树后序遍历的非递归算法

二叉树abcdefghij先序遍历_二叉树后序遍历的非递归算法给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。题解深搜/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() :

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

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

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

在这里插入图片描述
题解
深搜

/** * 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:
    const int INF = 0x3f3f3f3f;
    const int OINF = -0x3f3f3f3f;
    bool dfs(TreeNode * t,int &Min,int &Max){ 
   
        if(t->left == NULL && t->right == NULL){ 
   
            Min = t->val,Max = t->val;
            return true;
        }
        int tlMax = t->val,tlMin = t->val,trMax = t->val,trMin = t->val;
        Min = Max = t->val;
        if(t->left){ 
   
            if(!dfs(t->left,tlMin,tlMax))return false;
            else{ 
   
                if(tlMax >= t->val || tlMin >= t->val)return false;
                Min = min(tlMin,Min);
                Max = max(tlMax,Max);
            }
        }
        if(t->right){ 
   
            if(!dfs(t->right,trMin,trMax))return false;
            else{ 
   
                if(trMax <= t->val || trMin <= t->val)return false;
                Min = min(trMin,Min);
                Max = max(trMax,Max);
            }
        }
        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        int a = 0,b = 0;
        return dfs(root,a,b);
    }
};
  1. 仍然为深搜
    dfs(root,lower,upper):代表以root为根节点的树是否在lower和upper范围内
/** * 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:
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    bool dfs(TreeNode *root,long long lower,long long upper){ 
   
        if(root->left == NULL && root->right == NULL){ 
   
            if(root->val > lower && root->val < upper)return true;
            else return false;
        }
        if(root->val <= lower || root->val >= upper)return false;
        if(root->left && !dfs(root->left,lower,root->val))return false;
        if(root->right && !dfs(root->right,root->val,upper))return false;

        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        cout<<INF<<endl;
        return dfs(root,-INF,INF);
    }
};
  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:
    vector<int>res;
    bool dfs(TreeNode *root){ 
   
        if(root == NULL)return true;
        if(!dfs(root->left))return false;
        res.push_back(root->val);
        if(res.size() >= 2 && res[res.size() - 1] <= res[res.size() - 2])return false;
        if(!dfs(root->right))return false;

        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        return dfs(root);
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169155.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • cas算法是什么_对算法的认识

    cas算法是什么_对算法的认识应用原子操作类,例如AtomicInteger,AtomicBoolean …适用于并发量较小,多cpu情况下;Java中有许多线程安全类,比如线程安全的集合类。从Java5开始,在java.util.concurrent包下提供了大量支持高效并发访问的集合接口和实现类。如:ConcurrentMap、ConcurrentLinkedQueue等线程安全集合。引入问题那么问题来了,这些线程安全类的底层是怎么保证线程安全的,你可能会想到是不是使用同步代码锁synchronized?引入概念这些线

  • python把局部变量赋值给全局变量_局部变量不赋初值

    python把局部变量赋值给全局变量_局部变量不赋初值理解的都没问题。但我想聊聊出现这种情况的原因。在讲原因之前,需要先知道python中变量的搜索顺序,这个顺序是LGB(不考虑闭包情况)即local本地,global全局,builtin内建。比如:a=1deftest():a=3print(a)test()函数内声明了局部变量a,在打印中使用,在本地环境中命中,因此使用的是3。也许你会问这个知识点我早就知道了,这和本问题有什么关…

    2022年10月24日
  • 域名ssl证书怎么弄_nginx配置https证书

    域名ssl证书怎么弄_nginx配置https证书越来越多的第三方接入需要使用https了,很多时候不止到证书到那里免费申请,申请后怎么配置。免费证书和收费证书主要的差别有几点免费证书收费证书支持绑定域名数少支持绑定域名数多无保险费用有保险费用一年需要更换两年或三年可选颁发机构少更多的颁发机构证书免费申请的几个大平台阿里云腾讯云…

  • springboot 配置mybatis通用mapper

    springboot 配置mybatis通用mapper声明:此处为springboot配置mybatis的通用mapper方一共步其他多余操作不要有1添加mapper依赖一定要有以下依赖的jar包注意jar包版本,太高会导致功能不可用&lt;!–SpringBootMybatis依赖–&gt;&lt;dependency&gt;&lt;groupId&gt;org…

  • jar包和war包的区别

    jar包和war包的区别1.概念1.1jar包JAR包是类的归档文件,JAR文件格式以流行的ZIP文件格式为基础。与ZIP文件不同的是,JAR文件不仅用于压缩和发布,而且还用于部署和封装库、组件和插件程序,并可被像编译器和JVM这样的工具直接使用。2.2war包war包是JavaWeb程序打的包,war包里面包括写的代码编译成的class文件,依赖的包,配置文件,所有的网站页面,包括html,jsp等等。一个war包可以理解为是一个web项目,里面是项目的所有东西。2.目录结构

  • centos8.2内核版本_centos发行版本和内核版本

    centos8.2内核版本_centos发行版本和内核版本文章目录1.查看当前内核版本2.使用ELRepo仓库3.安装最新版内核4.设置以新的内核启动5.生成grub配置文件并重启系统6.验证新内核7.查看系统中已安装的内核8.删除旧内核9.参考文献1.查看当前内核版本使用的系统版本,当前日期CentOS最新版:1$cat/etc/redhat-release2CentOSLinuxrelease8.2.2004(Co…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号