二叉树的递归遍历比较简单，这里说一下非递归遍历，以中序遍历为例子。
非递归遍历主要用到栈来协助进行。对于一个二叉树，首先根节点入栈，如果有左儿子，则继续入栈，重复直到最左边的儿子，这时候此节点值为要遍历的第一个值，他父亲是在栈顶。所以我们做一次出栈操作 f = stack.pop()，并将 f.val 值存为第二个点，接下来要遍历 f.right，完成后栈的最后元素是 f 的父亲，继续做出栈操作。重复下去可以完成遍历。
def inorderTraversal(self, root): res = [] stack = [] while root!=None or stack!=[]: while root!=None: stack.append(root) root = root.left if stack!=[]: k = stack.pop() res.append(k.val) root = k.right return res
原文：http://www.cnblogs.com/tegongdete/p/6241312.html