【蓝桥Java每日一练】————6.二叉树的前中后序遍历(递归与迭代)(上)

简介: 今天给大家带来的每日一题是二叉树的前中后序遍历(其实是三题哈哈哈哈哈),二叉树是非常非常重要的基础结构,其中它的前中后序三种遍历又显得尤为基础和重要。每日一练的目的更多是和大家巩固基础能力,会则巩固之,不会更应学习之。

☀️1.浅聊如何理解递归


        递归这个东西,我相信很多兄弟根本弄不明白,有时候看到别人递归一行代码搞定的题目,自己不仅羡慕,还看不懂(没错这就是我了-。-)。


       首先我们要明确递归的三要素:


        1.确定递归函数的参数和返回值:我们需要确定在递归的过程中哪些参数是需要被处理的,而且我们还需要确定每次递归的返回值是什么,进而取确定递归函数的返回值类型。


        2.确定递归出口(终止条件):很多人在写递归方法时,总是遇到statckoverflow的错误,也就是栈溢出。递归既然是一直往下循环,那必然需要有一个循环出口,这和我们平常写的for和while是同一个道理。如何确定递归出口呢?这就要根据题目的意思去确定了。


       3.确定单层递归的要干啥:我相信这是大家最难处理的地方了,为什么会如此呢?要我来说就是多愁善感,因为许多兄弟太过去关心上一层和下一层干啥,让自己的脑袋也递归起来,最后脑袋栈溢出快疯掉了。所以大家一定要走出这个误区,这层有些什么东西,我们需要干些什么,干完了就不管了,千万不要过多关心其他层的事情。      


       同时在这给大家推荐一篇宝藏文章,也是让我自己真正学会递归三部曲的文章,相信一定会给大家带啦帮助:三道题套路解决递归问题


🍅1.二叉树的前序遍历(中左右)


给你二叉树的根节点 root ,返回它节点值的 前序 遍历。


题目链接:二叉树的前序遍历https://leetcode-cn.com/problems/binary-tree-preorder-traversal/            


🍅1.递归解法


           为什么先要和大家讲递归的解法呢?因为其实迭代解法也是利用的我们的栈statck,而递归本身就是隐式的使用了栈,这个相信大家也知道。而且二叉树的前中后三序遍历中,递归的解法都比迭代要简单的多,很多兄弟肯定说你别忽悠人。为什么呢?因为二叉树遍历的递归解法它的三要素都特别简单,函数返回值为void,参数就一个节点,递归出口也就节点为null,也非常容易,甚至连最难的处理逻辑也就只有一句话,那就是把当前节点的val放入到答案集合中。甚至会发现,前中后序的递归解法代码都差不多长一样,先理解递归再去写迭代会更加帮助我们理解。            


class Solution {
    //用来放答案的集合,设为全局变量
    List<Integer> list=new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
            if(root==null) return list;
            //注意我们一开始传入的节点是根节点
            test(root);
            return list;
    }
    public void test(TreeNode root){
        //递归出口
        if(root==null){
            return;
        }
        //先放入根节点
        list.add(root.val);
        //递归处理左子树
        test(root.left);
        //再处理右子树
        test(root.right);
    }
}

       这里要和兄弟们讲一下可能对于上面代码的疑问,后面的两种递归也是同理,就只讲一遍了。


1. list一定要是全局变量吗?


       这个当然不是,因为list在每层递归都会使用到它,所以我们也可以把他在preorderTraversal方法中实例化后,当作参数每次传递,当然写成全局变量会更加方便。    


2. 为什么要重新写一个test方法来递归?


       因为preorderTraversal方法需要返回一个list集合作为答案,而我们的递归逻辑其实是每次将元素放入到list中,是不需要返回值的,所以我们需要重写一个返回值为void方法来进行递归。


🍅2.迭代解法


             迭代其实也是利用了栈,只不过我们需要显示的去使用,这里我们用ArrayDeque充当栈比直接使用Statck更好。还要注意为什么先把右子节点入栈再入左子节点呢?因为栈是先进后出,前序遍历是中左右,为了让左节点先出所以得先放入右子节点。


class Solution {
    //用来存放答案的list
    List<Integer> list=new ArrayList<>();
    //用来当栈
    Deque<TreeNode> statck=new ArrayDeque<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return list;
        //先放入根节点
        statck.push(root);
        while(!statck.isEmpty()){
            //每次循环前先出栈一个元素
            TreeNode node=statck.pop();
            //然后加入到list中
            list.add(node.val);
            //再把该元素的右节点放入(空节点不如栈)
            if(node.right!=null){
                statck.push(node.right);
            }
            //再把左节点放入(空节点不如栈)
            if(node.left!=null){
                statck.push(node.left);
            }
        }
        return list;
    }
}


🍈 2.二叉树的中序遍历(左中右)


给定一个二叉树的根节点 root ,返回它的 中序 遍历。


题目链接:二叉树的中序遍历https://leetcode-cn.com/problems/binary-tree-inorder-traversal/


🍈1.递归解法


              代码和前序遍历差不多一样,只需要换一下顺序即可,可与前面的代码对照

class Solution {
    List<Integer> list=new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
            if(root==null) return list;
            test(root);
            return list; 
    }   
    public void test(TreeNode root){
        if(root==null) return;
        //这里我们先处理左子节点
        test(root.left);
        //再把跟节点放入到集合中
        list.add(root.val);
        //再处理右子节点
        test(root.right);
    }
}


相关文章
|
7月前
|
存储 监控 Java
《从头开始学java,一天一个知识点》之:数组入门:一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间?** - 看了三天教程,连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;,大脑突然空白 - 写出的代码总是莫名报NPE,却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」!我们承诺:每天1分钟,地铁通勤、午休间隙即可完成学习;直击痛点,只讲高频考点和实际开发中的「坑位」;拒绝臃肿,没有冗长概念堆砌,每篇都有可运行的代码标本。明日预告:《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧,帮助你快速掌握Java数组的精髓。
128 23
|
11月前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
4297 113
|
11月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
79 0
|
12月前
|
Java 程序员 编译器
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
279 3
|
12月前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
136 1
JAVA 递归文件夹
private void getAllFileInfo(String path) { File dirFile = new File(path); File[] files = dirFile.
734 0
|
18天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案