后序遍历二叉树.md

binary-tree-postorder-traversal（后序遍历二叉树）

知识点：树

题目描述

Given a binary tree, return the postorder traversal of its nodes' values.

For example: Given binary tree{1,#,2,3},

return[3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

给定一个二叉树，返回其后序遍历结果。

提示：递归解决方案是不值一提的，你选择迭代。

解题思路

首先明确什么是后序遍历：对于二叉树访问顺序为左-右-根，即为后序遍历。

递归方式很简单，这里说一下迭代的思路，考虑如下二叉树：

使用栈来解决非递归的后序遍历实现，重点在于以何种顺序入栈，由于是出栈的时候去遍历，所以按照后序遍历的顺序推导出入栈顺序应该是curNode、curNode.right、curNode.left，这样出栈的时候就能保证按照后序遍历的顺序了，另外需要使用一个preNode保存前一个遍历的节点，这样就能确定前一个被遍历的节点是否是当前节点的左/右子节点，如果是，说明其儿子已经被遍历了，这时就可以遍历自己了，否则不能遍历当前节点，需要先将当前节点的子节点入栈，最后的逻辑是：

初始：curNode=null，preNode=null，stack=new Stack()，stack.push(root)
while(stack不为空)：
		if curNode==null:
				curNode=stack.peek()
		if curNode 是叶子节点：
				print curNode.val
				preNode=curNode
				stack.pop()
				curNode=null
		else if preNode是curNode的直接子节点：
				print curNode.val
				preNode=curNode
				stack.pop()
				curNode=null
		else：
				stack.push(curNode.right)
				stack.push(curNode.left)
				curNode=curNode.left

代码

这里