🍈2.迭代解法
有兄弟肯定觉得，你递归解法只用在前序遍历的基础上改动一下即可，那你迭代解法一样改改不就行了吗？你还真别说，这样不行！因为前序是先处理中节点也就是根节点，是比较容易操作的，而我们的中序遍历是先处理左节点完后才能一个个倒退回来处理根节点。也就是说需要先将所有的左子节点放入栈后再一个个出栈，然后才能处理中节点和右节点。
class Solution { List<Integer> list=new ArrayList<>(); Deque<TreeNode> Stack=new ArrayDeque<>(); public List<Integer> 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 ，返回其节点值的 后序遍历 。
题目链接：二叉树的后序遍历https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
🍍1.递归解法
还是熟悉的配方还是熟悉的味道，换个位置（递归yyds）
class Solution { List<Integer> list=new ArrayList<>(); public List<Integer> 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<Integer> list=new ArrayList<>(); //用来当栈 Deque<TreeNode> statck=new ArrayDeque<>(); public List<Integer> 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.关于递归以及迭代的看法
看到这里肯定很多兄弟觉得，那我学个递归不就行了吗，又不用变化又简单。但其实这是不对的，如果你真的理解了递归的思想，那你也是可以写出迭代的做法，如果不能，那只能说明你在生搬硬套公式而已。在现在的面试中，涉及到这类题目，面试官都回要求使用迭代的做法，因为他知道你如果能写出迭代，递归也难不倒你。所以希望兄弟们一定要掌握号迭代的做法，真正去掌握二叉树的遍历能力，去分析三者的不同。
