☀️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); } }
