在这里会将树的前中后序遍历的非递归进行总结。
先记住一个要点， 所有的非递归和递归操作其实思路是一样的， 只是形式不一样。 根据我的实习经验来看，实际上工作日常编码如果能用递归尽量用递归，方便代码维护。
废话说完开始正篇：前中后序的非递归版本其实操作的流程是一样的 先附上高赞总结的代码
//1. 前序 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.add(p.val); // Add before going to children p = p.left; } else { TreeNode node = stack.pop(); p = node.right; } } return result; } //2. 中序 public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); p = p.left; } else { TreeNode node = stack.pop(); result.add(node.val); // Add after all left children p = node.right; } } return result; } //3. 后序 public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.addFirst(p.val); // Reverse the process of preorder p = p.right; // Reverse the process of preorder } else { TreeNode node = stack.pop(); p = node.left; // Reverse the process of preorder } } return result; }先看前序和中序的代码， 可以看见只有在加入集合的那行代码放的位置不一样， 这应该是一眼就能看懂思路的
再看后序。 后序操作的思路是左-> 右 -> 根. 但是我们现在得到的第一个节点是根节点。 关键是节点的成员变量都是子节点。 所以想直接做这种操作代价是很大的， 所以还是从根开始遍历， 但是在将值添加到元素的时候进行头插， 然后来逆转顺序， 这样我们只需要将遍历的机制变成 根 -> 右 -> 左 就可以了
