二叉树的遍历也是面试中的经典算法题，是算法相关岗位必须掌握的内容。
但是网上能找到的资料大部分是C/C++的，本文将以Python语言展示二叉树的三种遍历方式的递归与迭代实现方法。
假设有二叉树结构如下图所示：
二叉树
从列表（带终止符的中序列表）创建二叉树
# 定义二叉树类
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def create_tree(root, lst):
global i
# i不能超出lst范围，并且遇到#意味着到了叶节点，无法继续
if i > len(lst) -1 or lst[i] == '#':
return None
else:
data = lst[i]
root = TreeNode(data)
i += 1
root.left = create_tree(root.left, lst)
i += 1
root.right = create_tree(root.right, lst)
return root
if __name__ == "__main__":
lst = ['1','2','4','#','#','5','#','#','3','#','6','#']
root = TreeNode(0)
i = 0
root = create_tree(root, lst)
1. 前序遍历
1.1 递归实现
前序遍历的顺序是根节点->左子树->右子树，递归实现的代码很简单，按顺序递归打印即可：
凭直观查看，可以知道前序遍历的结果是[1,2,4,5,3,6]
def traversal(root,itype='preorder'):
# 递归遍历主函数
res = []
if itype == 'preorder':
preorder(root,res)
elif itype == 'inorder':
inorder(root, res)
elif itype == 'postorder':
postorder(root,res)
else:
print("Wrong itype.")
print(res)
def preorder(root, res):
# 前序遍历
if root is None:
return None
else:
res.append(root.val)
preorder(root.left,res)
preorder(root.right,res)
if __name__ == "__main__":
lst = ['1','2','4','#','#','5','#','#','3','#','6','#']
root = TreeNode(0)
i = 0
root = create_tree(root, lst)
traversal(root,itype='preorder')
output:
['1', '2', '4', '5', '3', '6']
结果符合预期。
1.2 迭代实现
迭代实现利用了栈的先进后出的性质，反顺序将节点加入，然后再输出。
def preorder_iter(root):
res, stack = [], []
if root is None:
return None
print("结点%s,入栈" % root.val)
stack.append(root)
while len(stack) > 0:
# 因为是中序遍历，所以找到一个节点便可以直接加入列表，然后再去找它的子树
node = stack.pop()
print("结点%s,出栈入表" % node.val)
res.append(node.val)
if node.right:
stack.append(node.right)
print("发现结点%s存在右结点，右结点%s入栈" % (node.val,node.right.val))
if node.left:
stack.append(node.left)
print("发现结点%s存在左结点，左结点%s入栈" % (node.val, node.left.val))
return res
if __name__ == "__main__":
lst = ['1','2','4','#','#','5','#','#','3','#','6','#']
root = TreeNode(0)
i = 0
root = create_tree(root, lst)
res = preorder_iter(root)
print(res)
output:
结点1,入栈
结点1,出栈入表
发现结点1存在右结点，右结点3入栈
发现结点1存在左结点，左结点2入栈
结点2,出栈入表
发现结点2存在右结点，右结点5入栈
发现结点2存在左结点，左结点4入栈
结点4,出栈入表
结点5,出栈入表
结点3,出栈入表
发现结点3存在右结点，右结点6入栈
结点6,出栈入表
['1', '2', '4', '5', '3', '6']
后面的中序和后序遍历代码类似，所以只介绍一下实现原理，不再逐步分析。
2. 中序遍历
中序遍历的顺序是：左子树-> 根节点 -> 右子树。就这个二叉树而言中序遍历的结果是：['4', '2', '5', '1', '3', '6']
中序遍历的递归实现没什么好讲的，和前序遍历几乎一样
2.1 递归实现
def inorder(root, res):
# 中序遍历
if root is None:
return None
else:
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
2.2 迭代实现
迭代实现同样是用到了栈的属性，先找到最左叶子节点，并将沿途的左节点都加入栈中，然后逐步回溯，加入父节点，如果父节点有右子树的话，再添加右子树。
def inorder_iter(root):
res, stack = [], []
node = root
if root is None:
return None
while node or len(stack) > 0:
if node:
# 一直向左，添加所有的左子树值
stack.append(node)
node = node.left
else:
# 逐步回退
node = stack.pop()
res.append(node.val)
# 如果node.right == None会继续回退
# 如果node.right != None则继续寻找node.right是否含有左子树
node = node.right
return res
3. 后序遍历
后序遍历的顺序是左子树-> 右子树-> 根节点，这棵树的后序遍历结果是：['4', '5', '2', '6', '3', '1']
3.1 递归实现
def postorder(root, res):
# 后序遍历
if root is None:
return None
else:
postorder(root.left,res)
postorder(root.right,res)
res.append(root.val)
3.2 迭代实现
后序遍历的迭代方法是在前序遍历的基础上改的，前序遍历是根节点->左子树->右子树，而后序遍历是左子树->右子树->根节点。
所以可以修改前序遍历代码，将遍历左右子树的顺序对调，即可用栈保存一个根节点->右子树->左子树的遍历序列，然后反序输出即可。
def postorder_iter(root):
# 后序迭代遍历
res, stack1, stack2 = [], [], []
if root is None:
return None
stack1.append(root)
while len(stack1) > 0:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
# 反序输出
while len(stack2) > 0:
node = stack2.pop()
res.append(node.val)
return res
