本文共 1915 字，大约阅读时间需要 6 分钟。

先写下这个问题的模式

def preorderTraversal(self, root):	if root == None: return []	re = []	insert root to stack s	while s not empty:		cur_root = top of stack s		s.pop()		how to handle cur_root		how to handle cur_root.left		how to handle cur_root.right

首先我们要把非空的root节点入栈，在循环里不断的判断出栈，然后处理栈顶元素及左孩子结点和右孩子结点。我们先看下当前的栈顶元素怎么处理，先根遍历的顺序是：【根 左 右】，而我们每次处理的栈顶元素的身份其实都恰好是根，所以我们就可以直接把这个根几点输出或放入结果容器中；那么其左孩子和右孩子如何处理呢？既然是模拟递归，那么肯定要入栈进行保存的，谁先入栈呢？考虑到栈的性质，我们应该让其右孩子先入栈，左孩子后入栈，这样，栈顶就是左孩子，下次先出栈的就是左孩子，这样就符合先根遍历的顺序了。

再回过头来看下在左右孩子没入栈之前，我们仅仅是获得了栈顶元素，该元素还依然在栈中，那么它在栈中还有意义吗？很明显没有意义了，因为它的信息我们已经输出，而其左右孩子在入栈后就再也不需要它了，所以就应该在左右孩子入栈前将其pop掉。

def preorderIter(self, root):		if None == root: return []		re = []; s = []		s.append(root)		while len(s):			cur_root = s.pop()			print cur_root.val			re.append(cur_root.val)			if cur_root.right:				s.append(cur_root.right)			if cur_root.left:				s.append(cur_root.left)		return re

同样，后根遍历也是如此，虽然后根的遍历是【左 右 根】，但是我们毕竟是知道根要放在哪里，区别就是子节点的入栈顺序的变化。

def postorderIter(self, root):		if None == root:			return		re = [] # store results		s = [] # node stack		s.append(root)		while len(s):			cur_root = s.pop()			re.insert(0,cur_root.val)			if cur_root.left:				s.append(cur_root.left)			if cur_root.right:				s.append(cur_root.right)		return re

麻烦点的应该是中根遍历【左 根 右】，如前所述，我们处理的当前栈顶节点是视为根结点的，但是这个根结点却不知该放在结果中的哪里，放在前面，前面应该是左的位置，放在右面，右边应该是右孩子的位置，放中间？哪里算中间？1-10, 2 是中间还是3是中间？我们不确定，因为左右孩子的个数我们无从得知。

看来此时的栈顶元素不能像先根和后根那样，直接输出，还得在栈里面挤一下才好，不然总不能直接丢弃。

之所以当前的栈顶根不能输出，是因为它的左还没有确定，那么我们只要把它的左都输出了，就可以确定当前根的位置了。

def inorderIter(self, root):		if None == root: return []		re = []		s = []		s.append(root)		while len(s):			cur_root = s[-1]			# push, until the last letf			while cur_root.left:				s.append(cur_root.left)				cur_root = cur_root.left			# pop, until one node has right			while len(s):				cur_root = s[-1]				print cur_root.val				re.append(cur_root.val)				s.pop()				if cur_root.right:					s.append(cur_root.right)					break		return re

转载地址：http://iumji.baihongyu.com/