Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [3,2,1].
后续遍历二叉树，主要是使用栈来非递归实现：
用 pre和cur来判断遍历的走向。
我们需要维护当前遍历的cur指针和前一个遍历的pre指针来追溯当前的情况（注意这里是遍历的指针，并不是真正按后序访问顺序的结点）。具体分为几种情况：
（1）如果pre的左孩子或者右孩子是cur，那么说明遍历在往下走，按访问顺序继续，即如果有左孩子，则是左孩子进栈，否则如果有右孩子，则是右孩子进栈，如果左右孩子都没有，则说明该结点是叶子，可以直接访问并把结点出栈了。
（2）如果反过来，cur的左孩子是pre，则说明已经在回溯往上走了，但是我们知道后序遍历要左右孩子走完才可以访问自己，所以这里如果有右孩子还需要把右孩子进栈，否则说明已经到自己了，可以访问并且出栈了。
（3）如果cur的右孩子是pre，那么说明左右孩子都访问结束了，可以轮到自己了，访问并且出栈即可。
时间复杂度为O(n),空间复杂度为O(nlogn).
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] res = [] stack = [root] pre = None cur = root while stack: cur = stack[-1] if not pre or pre.left == cur or pre.right == cur: #going down if cur.left: stack.append(cur.left) elif cur.right: stack.append(cur.right) else: stack.pop() res.append(cur.val) elif cur.left == pre and cur.right: #going up stack.append(cur.right) else: #going up res.append(cur.val) stack.pop() pre = cur return res
原文：http://www.cnblogs.com/sherylwang/p/5793078.html