java算法day11

  • 二叉树的递归遍历
  • 二叉树的非递归遍历写法
  • 层序遍历

递归怎么写?

按照三要素可以保证写出正确的递归算法:

1.确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2.确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。

3.确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。


前置必会

一定要会自己写出树的类定义

public class TreeNode{
	TreeNode left;
	TreeNode right;
	int val;
	TreeNode(){}
	TreeNode(int val){this.val = val}
	TreeNode(int val,TreeNode right,TreeNode left){
	this.val = val;
	this.left = left;
	this.right = right;
}

144.二叉树的前序遍历

递归写法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root,result);
        return result;
    }

    void dfs(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        result.add(root.val);
        dfs(root.left,result);
        dfs(root.right,result);
    }
    
}

非递归写法:
我认为就是记思路。
1.用一个栈作为辅助。
2.前序遍历是根左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。之所以是反过来是因为,这样出栈的时候才是根左右的顺序。直接来看图模拟
请添加图片描述
即每次在处理根节点的时候,将根节点出队,然后将其右孩子先进栈,再将左孩子进栈。
这样进行处理之后,出栈的结果就会是前序遍历的结果。

如果还是不懂,我建议直接结合代码,然后结合上面图,记下来这个做法。我觉得这个直接想是不好想的。

非递归其实就是用辅助数据结构,配合循环

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
    //结果集
        List<Integer> result = new ArrayList<>();
        //特判
        if(root == null){
            return result;
        }
        //创建辅助栈
        Deque<TreeNode> st = new ArrayDeque<>();
        //根节点先入栈
        st.push(root);
        //当栈不空的时候
        while(!st.isEmpty()){
        //先处理根节点,即将根节点出栈。这就对应着根
            TreeNode node = st.pop();
            //将出栈的根节点加入结果集
            result.add(node.val);
            //先将右节点加入栈中,可以这么想,早点加入,那么就晚点出。所以右节点出的时候,要比左节点晚,那么这里出也就是和上面节点出栈一个道理。所以这里就完成了根左右里面的根左。因为左节点进的晚,出的就早。
            if(node.right!=null){
                st.push(node.right);
            }
            //然后才是到左节点,晚点进就可以早点出。
            if(node.left!=null){
                st.push(node.left);
            }
        }
        
        return result;
    }
}

这是我第二写总结的流程:
1.初始化
创建一个空的结果列表
创建一个辅助栈
将根节点压入栈中

2.主循环: 当栈不为空时,执行以下操作:

a. 处理当前节点:
从栈中弹出一个节点
将该节点的值添加到结果列表中

b. 压入子节点:
如果该节点有右子节点,将右子节点压入栈中
如果该节点有左子节点,将左子节点压入栈中
返回结果列表

这种方法的关键点在于
根节点最先被处理,这符合前序遍历的"根-左-右"顺序。
右子节点先于左子节点入栈,这确保了左子节点会先于右子节点被处理。
这种非递归方法的优点是:

避免了递归调用的开销
对于深度很大的树,可以防止栈溢出
实现简单,易于理解
与中序遍历的非递归方法相比,前序遍历的非递归实现更为直观,因为它可以直接按照遍历顺序处理节点,而不需要像中序遍历那样先到达最左节点。

145.二叉树的后序遍历

递归写法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result  = new ArrayList<>();
        dfs(root,result);
        return result;
    }

    public void dfs(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        dfs(root.left,result);
        dfs(root.right,result);
        result.add(root.val);
    }
}

非递归写法:
这个解法是一个技巧解。
由于前序遍历是根左右,而后续遍历是左右根。所以如果调整一下前序遍历的顺序,先加左节点,再加右节点,那么得到的结果就是按根右左规则得到的。所以此时做翻转,那么得到的结果就是按左右根得到的结果。与后序遍历的结果不谋而合。
所以解法就是线序遍历调整左右入栈方式,然后再对最终结果做翻转。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.pop();
            result.add(node.val);
            if(node.left!=null){
                st.push(node.left);
            }
            if(node.right!=null){
                st.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

94.二叉树的中序遍历

递归写法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root,result);
        return result;
    }

    public void dfs(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        dfs(root.left,result);
        result.add(root.val);
        dfs(root.right,result);
    }
}

非递归写法:
看这个图,然后结合图片,记下这个做法:
请添加图片描述
1.初始化
创建一个空的结果列表和一个空的栈
将当前节点设置为根节点

2.主循环: 当当前节点不为空或栈不为空时,执行以下操作:

a. 左子树遍历
如果当前节点不为空
将当前节点压入栈
移动到左子节点

b. 节点处理
如果当前节点为空(即已经到达最左端)
从栈中弹出一个节点
将该节点的值添加到结果列表中
将当前节点移动到右子节点

3.返回结果列表

这种方法模拟了递归的过程:

首先尽可能深入地遍历左子树
然后处理节点本身
最后遍历右子树
使用栈来保存已经遍历过的父节点,以便在处理完左子树后能够回溯。

还是按代码思维走一遍,又和自己想的还是有一点区别。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    //结果集
        List<Integer> result = new ArrayList<>();
        //特判
        if(root==null){
            return result;
        }
        //辅助栈
        Deque<TreeNode> st = new ArrayDeque<>();
        //用一个遍历指针指向root
        TreeNode cur = root;
        //这里就是进递归处理的逻辑,循环条件决定了能不能递归处理下去。
        //cur!=null表明这个元素不空,可以进栈,!st.isEmpty(),是用来回溯的,表明栈中还有走过的元素需要进行处理。所以栈中走过的元素没处理完也要继续处理。
        while(cur!=null || !st.isEmpty()){
        //根据中序,左根右的走法,需要一路向最左下走。走的过程就一直入栈,保存之前的状态。如果cur==null,说明走到最左下的节点的左分支上了,也就是null。
            if(cur!=null){
                st.push(cur);
                cur = cur.left;
            }else{
            //不能继续往左走了才处理这里,这里就是开始回溯,回溯一下回到最左下的节点,此节点并不是null。那就把这个元素出栈,把这个元素的val加入结果集。由于每个元素都要左根右,这里处理了根节点,那还要往右节点走。下一波显然cur还是null,那么此时就会弹出沿着路线返回的根节点,往后都是这样。注意是依靠弹出的节点进行转移,因为栈里面的节点才是记录先前的状态,别自己瞎写一个。
                cur = st.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        //当st里面为空的时候,就是所有节点都处理完的时候。
        return result;
    }
}

102.二叉树的层序遍历

用队列。
看一个图就懂了。请添加图片描述
队列先进先出,符合一层一层遍历的逻辑。
下面的代码就是二叉树层序遍历的模板题,会这个模板,之后遇到只要是层序遍历的题,随便杀。

总的来说,这个解法看完,里面的len的处理我是当时没想到的。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        checkFun(root,result);
        return result;
    }

    public void checkFun(TreeNode node,List<List<Integer>> result){
    //特判
        if(node==null){
            return;
        }
        //辅助队列
        Deque<TreeNode> que = new ArrayDeque<>();
        //根节点先入队
        que.offerLast(node);
		//队列不空就代表流程还没有结束
        while(!que.isEmpty()){
        //记录一层元素的结果集
            List<Integer> itemList = new ArrayList<Integer>();
            //在一开始先记录长度,该长度即队列目前的长度,就是该层元素的个数。
            //记录len就是为了做一个界限,即处理完这一层元素后,就要收集一次结果集。
            int len = que.size();
            
            //这个循环做依次将该层元素出队,并扩展其左右节点加入队列当中。
            while(len>0){
            //先出队
                TreeNode tmpNode = que.pollFirst();
                //加入结果集
                itemList.add(tmpNode.val);
				//扩展左右节点,加入队列中。
                if(tmpNode.left!=null){
                    que.offerLast(tmpNode.left);
                }
                if(tmpNode.right!=null){
                    que.offerLast(tmpNode.right);
                }
                //做完之后该层元素数量要-1
                len--;
            }
            //处理完一层后记录一次结果。
            result.add(itemList);

        }
    }
}

107.二叉树的层序遍历Ⅱ

在上题的基础上将结果集翻转就结束了。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        checkFun(root,result);
        Collections.reverse(result);
        return result;
    }

    public void checkFun(TreeNode node,List<List<Integer>> result){
        if(node==null){
            return;
        }
        Deque<TreeNode> que = new ArrayDeque<>();
        que.offerLast(node);

        while(!que.isEmpty()){
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();
            
            while(len>0){
                TreeNode tmpNode = que.pollFirst();
                itemList.add(tmpNode.val);

                if(tmpNode.left!=null){
                    que.offerLast(tmpNode.left);
                }
                if(tmpNode.right!=null){
                    que.offerLast(tmpNode.right);
                }
                len--;
            }
            result.add(itemList);

        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790406.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

LabVIEW机器视觉技术在产品质量检测中有哪些应用实例

LabVIEW的机器视觉技术在产品质量检测中有广泛的应用&#xff0c;通过图像采集、处理和分析&#xff0c;实现对产品缺陷的自动检测、尺寸测量和定位校准&#xff0c;提高生产效率和产品质量。 1. 电子元器件质量检测 在电子制造业中&#xff0c;电子元器件的质量检测是确保产品…

AI绘画杀死了设计师!?恰恰相反……

与大多数人想象的不同&#xff0c;ChatGPT等各种AI工具爆火之后&#xff0c;受到冲击最大的居然是设计师、作家、翻译等具有创造性的工作&#xff0c;以体力劳动为主的蓝领反而最不易被替代。 以城市数据团做过的一项研究为例&#xff0c;他们对中国1639种职业进行了GPT替代风险…

蚁剑编码器编写——php木马免杀

蚁剑编码器编写——php木马免杀 我的想法是 木马要先免杀&#xff0c;能够落地&#xff0c;再去考虑流量层面的问题 举几个例子演示一下 命令执行与代码执行是有比较大的区别&#xff0c;蚁剑执行的是php代码&#xff0c;而system&#xff0c;proc_open,passthru,exec,shell_…

【C++深度学习】多态(概念虚函数抽象类)

✨ 疏影横斜水清浅&#xff0c;暗香浮动月黄昏 &#x1f30f; &#x1f4c3;个人主页&#xff1a;island1314 &#x1f525;个人专栏&#xff1a;C学习 &#x1f680; 欢迎关注&#xff1a;&#x1f44d;点赞 &…

比curl更直观的网站性能测试工具httpstat——筑梦之路

GitHub - davecheney/httpstat: Its like curl -v, with colours. wget https://raw.githubusercontent.com/reorx/httpstat/master/httpstat.pymv httpstat.py /usr/bin/httpstat #移动到环境变量路径chmod x /usr/bin/httpstat #添加可执行权限 exec bash #重置当前bash进…

Python爬虫教程第3篇-解决使用reqeusts遇到的ProxyError异常

起因 问题出现在windows电脑上&#xff0c;我用mac执行程序的时候并不会报错&#xff0c;但是如果在windows上的时候&#xff0c;大部分windows电脑会报错&#xff0c;而有些版本低的windows电脑又不会报错。 异常栈信息 HTTPSConnectionPool, Cannot connect to proxy, no …

《昇思25天学习打卡营第14天|计算机视觉-ShuffleNet图像分类》

FCN图像语义分割&ResNet50迁移学习&ResNet50图像分类 当前案例不支持在GPU设备上静态图模式运行&#xff0c;其他模式运行皆支持。 ShuffleNet网络介绍 ShuffleNetV1是旷视科技提出的一种计算高效的CNN模型&#xff0c;和MobileNet, SqueezeNet等一样主要应用在移动端…

海外路人采访:提高了广告推广的曝光率-华媒舍

在当今社交媒体和网络广告的世界中&#xff0c;我们经常会听到关于火爆推广的故事&#xff0c;但人们对其背后的机制却知之甚少。本文将通过采访七位路人的经历&#xff0c;揭示这些火爆推广背后的秘密&#xff0c;帮助读者更好地理解和应对这一现象。 路人一&#xff1a;微博热…

昨日头条管理系统设计

设计一个“昨日头条”类似的内容管理系统时&#xff0c;我们可以借鉴内容管理系统设计原则&#xff0c;并针对“昨日头条”这类新闻资讯类应用的特点进行定制化设计。以下是一些关键点&#xff1a; 1. 内容采集与整合 智能抓取&#xff1a;设计爬虫系统自动抓取国内外各大新闻…

鸿蒙语言基础类库:【@ohos.util.Vector (线性容器Vector)】

线性容器Vector 说明&#xff1a; 本模块首批接口从API version 8开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 Vect…

【记录】LaTex|LaTex 代码片段 Listings 添加带圆圈数字标号的箭头(又名 LaTex Tikz 库画箭头的简要介绍)

文章目录 前言注意事项1 Tikz 的调用方法&#xff1a;newcommand2 标号圆圈数字的添加方式&#xff1a;\large{\textcircled{\small{1}}}\normalsize3 快速掌握 Tikz 箭头写法&#xff1a;插入点相对位移标号node3.1 第一张图&#xff1a;插入点相对位移3.2 第二张图&#xff1…

java.lang.NullPointerException: null cannot be cast to non-null type kotlin.Int

java.lang.NullPointerException: null cannot be cast to non-null type kotlin.Int fun main(args: Array<String>) {var any1: Any?any1 nullval n1 any1 as? Int ?: -2024println(n1)kotlin.runCatching {var any2: Any?any2 nullval n2 any2 as Intprintln(…

base SAS programming学习笔记10(combine data)

1.一对一合并 基本格式如下&#xff1a; data output-data-set; set data-set1; set data-set2;(data-set1和data-set2可以是相同的数据集&#xff0c;可以添加多个set 语句来实现上述的一对一合并) run; 输出数据集结果如下&#xff1a; a.会包含所有输入数据的变量名&#x…

多头注意力的公式理解

多头注意力 (Multihead Attention) 多头注意力是一种通过并行使用多个注意力机制来增强模型能力的方法。每个注意力机制被称为一个“头”&#xff08;head&#xff09;。这种机制使得模型可以在不同的子空间中并行计算注意力&#xff0c;从而捕捉输入数据中不同范围的依赖关系…

如何写好品牌宣传稿提升品牌曝光?看这篇文章就够了

在这个信息爆炸的时代&#xff0c;一句精炼而富有力量的宣传语&#xff0c;足以让品牌在万千竞争者中脱颖而出。撰写一篇成功的品牌宣传稿&#xff0c;不仅是对文字艺术的驾驭&#xff0c;也是对品牌灵魂的深刻洞察与精准传达&#xff0c;更是连接品牌与消费者情感与认知的桥梁…

华为防火墙上的配置(1)

实验拓扑图 实验要求&#xff1a; 1、DMZ区内的服务器&#xff0c;生产区仅能在办公时间内&#xff08;9&#xff1a;00-18:00)可以访问&#xff0c;办公区的设备全天可以访问 2、生产区不允许访问互联网&#xff0c;办公区和游客区允许访问互联网 3、办公区设备10.0.2.10不…

MT5016A-ASEMI逆变焊机专用MT5016A

编辑&#xff1a;ll MT5016A-ASEMI逆变焊机专用MT5016A 型号&#xff1a;MT5016A 品牌&#xff1a;ASEMI 封装&#xff1a;KBPC-4 批号&#xff1a;2024 现货&#xff1a;50000 正向电流&#xff08;Id&#xff09;&#xff1a;50A 反向耐压&#xff08;VRRM&#xff0…

位运算在数据库中的运用实践-以MySQL和PG为例

目录 前言 一、两种不同的数据库设计 1、状态字段存储JSON 2、使用位运算 二、数据库中的位运算实践 1、MySQL中的位运算实践 2、PostgreSQL中位运算实践 三、总结 前言 最近在解决某用户的一个业务需求时&#xff0c;遇到一个很有意思的场景。首先先跟大家分享一下需求…

记录一次mysql死锁问题的分析排查

记录一次死锁问题的分析排查 现象 底层往kafka推送设备上线数据应用层拉取设备上线消息,应用层有多个消费者并发执行将设备上线数据同步数据库表pa_terminal_channel日志报&#xff1a;&#xff08;Cause: com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: …

skywalking-1-服务端安装

skywalking很优秀。 安装服务端 skywalking的服务端主要是aop服务&#xff0c;为了方便查看使用还需要安装ui。另外采集的数据我们肯定要存起来&#xff0c;这个数据库就直接用官方的banyandb。也就是aop、ui、banyandb都使用官方包。 我们的目的是快速使用和体验&#xff0c…