二叉树中的深度搜索

简介: 二叉树中的深度搜索

力扣2331.计算布尔二叉树值

深度搜索:是要进入最下面

二叉树直接往递归上去想(易写,不易想)

 public boolean evaluateTree(TreeNode root) {
    if(root.left==null||root.right==null){
         return root.val==0?false:true;
     } 
//先拿到左子树,然后返回
     boolean left=evaluateTree(root.left);
//再拿到右子树,然后返回
     boolean right=evaluateTree(root.right);
//从根部开始走
     return root.val==2?left|right:left&right;
    }

力扣129.求根节点到叶子节点数字之和

这道题的思路,我是没想出来,然后看视频教

怎么说从上面走到下面,再从下面回归到上面

public int sumNumbers(TreeNode root) {
      return dfs(root,0);
    }
    public int dfs(TreeNode root,int preSum){
//及时更新结果第一步,把当前值传递给下一个递归的
        preSum=preSum*10+root.val;
     if(root.left==null&&root.right==null){
         return preSum;
     }
     int sum=0;
//
    if(root.left!=null) sum=sum+dfs(root.left,preSum);
    if(root.right!=null) sum=sum+dfs(root.right,preSum);
     return sum;
 
    }

力扣814.二叉树剪枝

public  static TreeNode pruneTree(TreeNode root) {
        if(root.left==null&&root.right==null){
            if(root.val==0){
                root=null;
            }
            return root;
        }
      if(root.left!=null) {
          root.left=pruneTree(root.left);}
      if(root.right!=null) {
          root.right = pruneTree(root.right);
      }
      if(root.left==null&&root.right==null&&root.val!=1){
          return null;
      }
        return root;
    }

这几个递归,已经能摸索出来一点东西,假如两边都是null,还要记得判断他的值,假如他是0,才可以让他是空,然后判断叶子结点之后,我们也要判断,假如他作为根节点,需不需要判断呢?答案也是必然的,所以当根的左右都为空,根也是0,那么这个根也可以返回null。

力扣98.验证二叉搜索树

我自己的思路开始肯定不是知道什么中序遍历,刚开始我是想要去递归,但是发现这个函数类型是boolean,但是boolean这个类型,我不能根据这个返回TreeNode,那么也就是说我不能通过递归的结果比较数值,那么我就想再去定义一个函数(类型TreeNode),暂时思路是这样,但是没有写出来。原因:

开始的想法:这个是错误的,看下面图片,作者说的很清楚,不可以这么写

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val)
        return false;
    return isValidBST(root.left) && isValidBST(root.right);
}
 
作者:数据结构和算法
链接:https://leetcode.cn/problems/validate-binary-search-tree/solutions/441173/san-chong-jie-jue-fang-shi-liang-chong-ji-bai-liao/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

二叉搜索树中序遍历的结果,是一个有序的序列

1.全局变量的优势

2.回溯:递归之后的返回值,就叫回溯(牛马,一点不高级)

3.剪枝:当发现不是二叉搜索树的时候,就没有必要管其他节点(意义是加快搜索过程)

策略一:左子树是二叉搜索树,当前节点符合二叉搜索树的定义,右子树也是二叉搜索树。(关注自己怎么判断,只需要和prev做判断即可,无需和后面这些数做比较,因为和后面这些数做比较的过程中序遍历已经完成了。)

策略二:剪枝,当找到不符合的情况,直接返回false即可。

引入一个知识:

class Solution {
   //-231 <= Node.val <= 231 - 1,他有可能拿这种数字恶心你,所以你设置一个最小的,那么也就是Long类型的最小值
    long prev=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    if(root==null)return true;
    boolean left=isValidBST(root.left);
    //这就是剪枝,就是不用去多考虑一些没用的情况
    if(left==false) return false;
    boolean cur=false;
    if(root.val>prev)cur =true;
//剪枝的思想。就是简单的不用考虑一些东西
    if(cur==false) return false;
    prev=root.val;
    boolean right=isValidBST(root.right);
    return left&&cur&&right;
 
    }

中序遍历:左根右(左树节点小于根,根小于右边节点)

思路:因为中序遍历之后,是一个有序的,所以我们只需要保证按照中序遍历,保存他的前一个值,然后用前一个值和他比较,就可以比较出是true,还是false。

遍历左树的时候,还是看左树是true还是false,怎么看,看左树的节点跟他的前一个值比较,假如比他大,那么就返回真。假如是假,那么就说明树不是二叉搜索树,然后更新前一个值,让前一个值等于当前值,再看他的右子树,右子树是开始和根节点比较,(根节点和最后一个左叶子结点比较)


目录
打赏
0
1
1
0
27
分享
相关文章
linux查看内存信息
在Linux中检查内存使用:`free -h`或`-m`显示简洁内存统计;`cat /proc/meminfo`获取详细信息;`top`或`htop`(如果安装)实时监控进程内存占用;`vmstat`查看虚拟内存统计;`sar -r`(需要sysstat)报告系统内存活动。图形工具如Gnome System Monitor提供可视化界面。
398 4
【软件设计师-从小白到大牛】上午题基础篇:第五章 结构化开发方法
在结构化分析中,用数据流图描述 数据在系统中如何被传送或变换,以及如何对数据流进行变换的功能或子功能,用于对功能建模。 数据字典有以下4类条目:数据流、数据项、数据存储和基本加工。
366 0
ELK搭建(五):linux系统日志监控平台搭建
现在的生产系统多使用linux系统,在实际生产过程中我们除了需要监控一些业务日志之外,有时也需要监控linux系统本身的日志,来帮助我们进行一些排错和判断。那么这一期,我们就针对linux系统日志监控平台的搭建来进行讲解 与往期一样,我们针对实际搭建教程更多是快速搭建为主,不做过多的原理性讲解,这一类讲解我们放到后期单独开几期博客来探讨。
1253 0
ELK搭建(五):linux系统日志监控平台搭建
基于SQL Server / MySQL进行百万条数据过滤优化方案
对百万级别数据进行高效过滤查询,需要综合使用索引、查询优化、表分区、统计信息和视图等技术手段。通过合理的数据库设计和查询优化,可以显著提升查询性能,确保系统的高效稳定运行。
186 9
Oliva:语音RAG革命!开源多智能体秒解复杂搜索,实时对讲颠覆传统
Oliva是一款基于Langchain和Superlinked的开源语音RAG助手,通过实时语音交互在Qdrant向量数据库中进行语义搜索,支持多智能体协作处理复杂查询任务。
210 4
Oliva:语音RAG革命!开源多智能体秒解复杂搜索,实时对讲颠覆传统
深入探索Linux内核的内存管理机制
本文旨在为读者提供对Linux操作系统内核中内存管理机制的深入理解。通过探讨Linux内核如何高效地分配、回收和优化内存资源,我们揭示了这一复杂系统背后的原理及其对系统性能的影响。不同于常规的摘要,本文将直接进入主题,不包含背景信息或研究目的等标准部分,而是专注于技术细节和实际操作。
使用 Python 实现深度学习模型:智能食品生产线优化
使用 Python 实现深度学习模型:智能食品生产线优化
151 13
给技术新人的ODPS优化建议
数据开发基本都是从陌生到熟悉,但是写多了就会发现各种好用的工具/函数,也会发现各种坑,本文分享了作者从拿到数据到数据开发到数据监控的一些实操经验。
96332 127
自动化测试项目学习笔记(四):Pytest介绍和使用
本文是关于自动化测试框架Pytest的介绍和使用。Pytest是一个功能丰富的Python测试工具,支持参数化、多种测试类型,并拥有众多第三方插件。文章讲解了Pytest的编写规则、命令行参数、执行测试、参数化处理以及如何使用fixture实现测试用例间的调用。此外,还提供了pytest.ini配置文件示例。
328 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等