题目链接: 二叉树后序非递归遍历实现
前置说明：阅读本文的读者建议先参考我在数据结构专栏里的“二叉树前序、中序遍历非递归实现”这篇博客，因为本文是在那篇博客的基础上延伸的，否则你会觉得我写的是神马玩意@@
1.1-图文详解
1.2-看图说明
由于图解很长，为了便于读者阅读，我用一张图说明阅读图解的的顺序。
注：一定是上图红色虚线框里面的部分的执行完蓝色框的代码后变成下图红色虚线框里面的。
1.3-完整代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
while(cur != null || stack.isEmpty() == false){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || prev == top.right){
stack.pop();
list.add(top.val);
prev = top;
}else{
cur = top.right;
}
}
return list;
}
}
1.4-个人感悟
起初看视频课听老师讲这道题时，不到20分钟就完事了，我也以为听懂了明白了。直到我自己动手画图厘清里面的逻辑关系，我才发现·······光画上面的图解我用了不止5个小时！！！对于我个人而言，严格意义上用伪代码来叙述解题思路的话，我是可以做到的，但是具体到代码实现时感觉很棘手。
特别是“节点root如果被记录需要root .right != null 或者 root.right 被记录过”，这个“root.right被记录过”怎么用代码实现？
图解里用了prev节点来标记最近一次被记录的结点，并利用top的迭代，从而实现“root.right被记录过”这个伪代码。我认为这是这个题的精华所在。
ps：我初学数据结构没多久，弄懂这道题既兴奋又有点小小的失落感。失落在于画图居然花了这么久时间，而老师轻描淡写几分钟就讲完了。或许不能用太严苛的标准要求自己吧@@，毕竟武林高手也是需要多年的锤炼才成。当然通过画图逐步剖析过程，让我对后序非递归遍历的过程又有了新的认识，有些体悟真的不能完全在图解中体现，那是只可意会不可言传的内化的东西。
仅以此文记录自己学习数据结构的心得，也希望本文的分享对你有所帮助~~