二叉树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)
blank

相关推荐

  • springboot概述_已进入fastboot

    springboot概述_已进入fastbootSpringBoot概述SpringBoot是由Pivotal团队提供的全新框架,其设计目的是用来简化Spring应用的创建、运行、调试、部署等。使用SpringBoot可以做到专注于Spring应用的开发,而无需过多关注XML的配置。SpringBoot使用“习惯优于配置”的理念,简单来说,它提供了一堆依赖打包,并已经按照使用习惯解决了依赖问题。使用SpringBoot可以不用或者只…

  • linux 时间戳转换/dmesg 时间转换

    linux 时间戳转换/dmesg 时间转换dmesg时间转换dmesg输出的格式不易查看,可以通过命令进行转换。记录如下:时间查看:date-d”1970-01-01UTC`echo”$(date+%s)-$(cat/proc/uptime|cut-f1-d”)+12288812.926194″|bc`seconds”/proc/uptime详解在Linux中

  • 《Qt 实战一二三》

    《Qt 实战一二三》Qt基础与实战,主要包含:环境搭建、信号槽、事件机制、数据类型、常用部件/布局、对话框、QPainter绘图等内容。

  • mbus主站电路设计_proteus子电路模块

    mbus主站电路设计_proteus子电路模块1Mbus接收发送机制对于主从式通信系统,因从机之间不能直接交换信息,只能通过主机来转发,此时采用MBus可以实现对从机的相关数据进行采集,并传递至集中器,然后再传递至总站。它由主机从机和两线制总线组成。MBus总线是一种半双工通信总线,其可以通过集中器实现给终端仪表远程供电。1.1发送由集中器向终端仪表传输的信号采用电压值的变化来表示,即集中器向终端仪表发送的数据码流是一种电压脉冲序列,用+36V表示逻辑“1”,用+24V表示逻辑“0”。在稳态时,线路将保持“1”状态。

    2022年10月15日
  • stringutil.isnotempty_中低腰和低腰的区别

    stringutil.isnotempty_中低腰和低腰的区别学习中遇到了这个地方,搜了一下,这位仁兄总结的挺详细,就粘了过来原文链接(https://www.cnblogs.com/dixinyunpan/p/6088612.html)isNotEmpty(str)等价于str!=null&&str.length>0isNotBlank(str)等价于str!=null&&str…

  • Hive简介

    Hive简介

    2021年11月27日

发表回复

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

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