1. 定义

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 遍历

2.1 先序遍历

2.1.1 递归

def pre(node):
    if node is None:
        return
    print(node.val)
    pre(node.left)
    pre(node.right)

2.1.2 非递归

2.3 中序遍历

2.3.1 递归

def mid(node):
    if node is None:
        return
    mid(node.left)
    print(node.val)
    mid(node.right)

2.3.2 非递归

2.3 后序遍历

2.3.1 递归

def post(node):
    if node is None:
        return
    post(node.left)
    post(node.right)
    print(node.val)

2.3.2 非递归

2.4 测试

# 定义结点
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node7 = TreeNode(7)
# 构建树
root = node1
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7
print(------先序遍历（递归）------)
pre(root)
# 1 2 4 5 3 6 7
print(------中序遍历（递归）------)
mid(root)
# 4 2 5 1 6 3 7
print(------后序遍历（递归）------)
post(root)
# 4 5 2 6 7 3 1

3. 重建二叉树

只能由前中序或后中序才能重建二叉树（必须有中序遍历找到根结点所在位置）。

3.1 由前、中序遍历重建二叉树

def tree_by_pre_mid(pre, mid):
    if (len(pre) == 0) or (len(mid) == 0) or (len(pre) != len(mid)):
        return
    root = TreeNode(pre[0])
    # 在中序遍历中找到根结点位置
    i = mid.index(pre[0])
    root.left = tree_by_pre_mid(pre[1:i+1], mid[:i])
    root.right = tree_by_pre_mid(pre[i+1:], mid[i+1:])
    return root

3.2 由后、中序遍历重建二叉树

def tree_by_post_mid(post, mid):
    if (len(post) == 0) or (len(mid) == 0) or (len(post) != len(mid)):
        return
    root = TreeNode(post[-1])
    # 在中序遍历中找到根结点位置
    i = mid.index(post[-1])
    root.left = tree_by_post_mid(post[:i], mid[:i])
    # -1 不能省，否则结果不对
    root.right = tree_by_post_mid(post[i:-1], mid[i+1:])
    return root

3.3 测试

pre_order_list = [1, 2, 4, 5, 3, 6, 7]
mid_order_list = [4, 2, 5, 1, 6, 3, 7]
post_order_list = [4, 5, 2, 6, 7, 3, 1]
root = tree_by_pre_mid(pre_order_list, mid_order_list)
post(root)
# 4 5 2 6 7 3 1
root = tree_by_post_mid(post_order_list, mid_order_list)
pre(root)
# 1 2 4 5 3 6 7