前言
今天做了关于二叉树的后序遍历题目，我的计划是先将二叉树的前中后三种遍历算法掌握，然后再做关于二叉树的其他题目。
今天不将递归和迭代代码分开啦！一起讲了。
我最近的感悟：题目看不懂，那就直接去看题解，题解还看不懂，那就直接看代码，然后带一个例子把程序走一遍，最后在翻过头来看题解，我想看不太懂也差不多了。
重点：看懂之后记得多敲几遍，最好形成条件反射，一看到这个题就知道代码是什么了。
目标：不求所有的都会，我们也做不到，只求我们做过的你还能做出来就足够了。
本文目的
掌握二叉树的后序遍历过程。
掌握后序遍历的递归和迭代代码。
希望亲爱的读者，看完本文章，能掌握这两种算法。
正文
- 预备知识1：
- 默认读者已了解二叉树的基本概念。
- 预备知识2：
- 后序遍历的顺序是什么呢？
- 左孩子-》右孩子-》父结点
- 上例子
- 上图的顺序为[4,5,2,6,3,1]
- 读者有任何问题，欢迎下方留言，我们一起学习喽！
- 1.题目如下
- 2.代码实现
- 思想：后序遍历中各父结点是最后一个访问，根节点是所有元素访问完之后才会访问。
- 迭代代码
var postorderTraversal = function(root) { let res = [];//最后要返回的数组 let stack = [];//遍历过程中遇到的元素结点 while(root || stack.length){ while(root){ res.unshift(root.val);//这个是数组的一个方法，可以理解成头插法，往首部插入 stack.push(root); root = root.right; } let node = stack.pop(); root = node.left; } return res; };
解释
这个代码是先找父结点，然后一直找的是父结点的右孩子，不知道读者看出来了吗？
每遇到一个结点，就用头插法，把该结点的val值插入到返回的数组中。这个过程，就是算法的核心，这个地方理解了，那么这个代码也就通了。我先和读者一起走一遍，起初，我们先判断root是否为null，若是null，那么不进入循环，直接return；反之，将根节点的val头插法到res数组中，将根节点整体入stack数组中，然后找它的右孩子，如果有的话，继续循环，这个地方，我们可以知道，每循环一次，总是将一个结点的val插入到到res数组的第一个位置中。
总结 :根元素的val值被放到了res数组的最后一个，我们找的顺序是父结点-》右孩子-》左孩子，输出顺序就是左孩子-》右孩子-》父结点喽！(因为我们是用的头插法)
这里我们上边的图再来说一遍。请读者耐住性子，相信我，看完不懂你捶我。
res数组中的元素变化过程
- [1]
- [3,1]
- [6,3,1]
- [2,6,3,1]
- [5,2,6,3,1]
- [4,5,2,6,3,1]
- 这不就是我们想要的的后序遍历顺序吗？
- 结束啦，有任何问题欢迎下方留言。
- 递归代码
var postorderTraversal = function(root) { let res = [];//要返回的数组 const traversal = (root01)=>{ if(root01 == null) return;//找到尽头，需要另换路 traversal(root01.left);//遍历左子树 traversal(root01.right);//遍历右子树 res.push(root01.val);//左右子树遍历结束就只剩中间喽！ } traversal(root); return res; };
- 递归有问题的，小嘟建议你做题的时候可以画下图，边看代码边画图，不一会你就懂啦。
结尾
- 如果你认真看完本文章，我相信你肯定会的。
- 下次出一篇前序遍历的迭代和递归代码，然后看能不能找出它们之间的共性。
- 本人笔拙，有的地方写的不对，欢迎指出，谢谢！！！
- 最后，祝大家看完该文章有所收获，我们下期再见。
