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

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

⭐️引言⭐️

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

⭐️精彩回放⭐️

2022.1.9——Java每日一练【蓝桥Java每日一练】————5.按键持续时间最长的键2022.1.8——Java每日一练【蓝桥Java每日一练】————4.移除元素2022.1.7——Java每日一练【蓝桥Java每日一练】————3.合并两个有序链表2022.1.5——Java每日一练【蓝桥Java每日一练】————2.替换所有的问号2022.1.4——Java每日一练【蓝桥Java每日一练】—————1.一周中的第几天

⭐️目录⭐️

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

1.二叉树的前序遍历（中左右）

        1.递归解法 

        2.迭代解法 

 2.二叉树的中序遍历（左中右）

         1.递归解法

         2.迭代解法

3.二叉树的后序遍历（左右中）

        1.递归解法

        2.迭代解法

 4.关于递归以及迭代的看法

---

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

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

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

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

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

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

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

1.二叉树的前序遍历（中左右）

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

题目链接：二叉树的前序遍历            

        1.递归解法 

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

class Solution {
    //用来放答案的集合，设为全局变量
    List list=new ArrayList<>();
    public List 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 list=new ArrayList<>();
    //用来当栈
    Deque statck=new ArrayDeque<>();
    public List 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 ，返回它的 中序 遍历。

题目链接：二叉树的中序遍历

         1.递归解法

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

class Solution {
    List list=new ArrayList<>();
    public List 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);
    }
}

         2.迭代解法

              有兄弟肯定觉得，你递归解法只用在前序遍历的基础上改动一下即可，那你迭代解法一样改改不就行了吗？你还真别说，这样不行！因为前序是先处理中节点也就是根节点，是比较容易 *** 作的，而我们的中序遍历是先处理左节点完后才能一个个倒退回来处理根节点。也就是说需要先将所有的左子节点放入栈后再一个个出栈，然后才能处理中节点和右节点。

class Solution {
    List list=new ArrayList<>();
    Deque Stack=new ArrayDeque<>();
    public List inorderTraversal(TreeNode root) {
           while(root!=null||!Stack.isEmpty()){
               //一个while循环把左节点疯狂放入到栈中
               while(root!=null){
                   Stack.push(root);
                   root=root.left;
               }
               //最下面的左子节点出栈，获取他
               root=Stack.pop();
               //加入list中
               list.add(root.val);
               //去处理右节点
               root=root.right;
           }
           return list;
    }
}

         我自己觉得这串代码刚开始还是有点难理解的，光说也是很难理解的，但是如果大家能用草稿纸自己画个栈debug一下，就能非常快的理解，还是希望大家开发一下动手能力多多理解。

3.二叉树的后序遍历（左右中）

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

题目链接：二叉树的后序遍历

        1.递归解法

                还是熟悉的配方还是熟悉的味道，换个位置（递归yyds）

class Solution {
    List list=new ArrayList<>();
    public List postorderTraversal(TreeNode root) {
            test(root);
            return list;
    }
    public void test(TreeNode root){
        if(root==null) return;
        test(root.left);
        test(root.right);
        list.add(root.val);     
    }
}

        2.迭代解法

               后序的迭代就比较有趣了，我们都知道我们写了前序的遍历顺序是中左右，在里面我们有个入栈的步骤，是先入右再入左，如果我们先入左再入右是不是遍历顺序就是中右左，这时我们把得到的答案list整个反过来，是不是就变成了左右中，也就是我们的后序遍历了。大家对比一下代码就能发现很神奇了！

class Solution {
    //用来存放答案的list
    List list=new ArrayList<>();
    //用来当栈
    Deque statck=new ArrayDeque<>();
    public List postorderTraversal(TreeNode root) {
        if(root==null) return list;
        statck.push(root);
        while(!statck.isEmpty()){
            TreeNode node=statck.pop();
            list.add(node.val);
            //先放左再放右
            if(node.left!=null){
                statck.push(node.left);
            }
            if(node.right!=null){
                statck.push(node.right);
            } 
        }
        //反转链表
        Collections.reverse(list);
        return list;
    }
}

 4.关于递归以及迭代的看法

         看到这里肯定很多兄弟觉得，那我学个递归不就行了吗，又不用变化又简单。但其实这是不对的，如果你真的理解了递归的思想，那你也是可以写出迭代的做法，如果不能，那只能说明你在生搬硬套公式而已。在现在的面试中，涉及到这类题目，面试官都回要求使用迭代的做法，因为他知道你如果能写出迭代，递归也难不倒你。所以希望兄弟们一定要掌握号迭代的做法，真正去掌握二叉树的遍历能力，去分析三者的不同。