二叉树的遍历也是面试中的经典算法题，是算法相关岗位必须掌握的内容。

但是网上能找到的资料大部分是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