二叉树作为FDS课程最核心的数据结构之一，要求每个人都掌握！ 这是一道简单的二叉树问题！ 我们将给出一颗二叉树，请你输出它的三种遍历，分别是先序遍历，中序遍历，后序遍历！ 输入格式: 二叉树将以这样的形式给出： 第一行给出一个正整数N（N<=100)，表示二叉树上的节点个数！ 接下来N行，每行包含三个整数，i，l，r，分别代表第i个节点的左右孩子！ 如果它的左/右孩子为空，则在对应位置给出-1！ 题目保证1是根节点！ 输出格式: 请你输出它的三种遍历！ 第一行输出先序遍历，第二行输出中序

遍历，第三行输出后序遍历，每行节点之间用空格隔开。

算法1

递归遍历二叉树，先序遍历直接输出父节点，中序遍历先递归左子树再输出，后序遍历先递归左右子树再输出。

时间复杂度

遍历每个节点，时间复杂度为O(n)。

Python 代码

n = int(input())
tree = {}
for i in range(n):
    fa, lch, rch = map(int, input().split())
    tree[fa] = (lch, rch)

def preorder(node):
    if node == -1:
        return
    print(node, end=' ')
    preorder(tree[node][0])
    preorder(tree[node][1])

def inorder(node):
    if node == -1:
        return
    inorder(tree[node][0])
    print(node, end=' ')
    inorder(tree[node][1])

def postorder(node):
    if node == -1:
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end=' ')

preorder(1)
print()
inorder(1)
print()
postorder(1)
print()

算法2

使用栈模拟递归遍历二叉树，先序遍历先将根节点入栈，然后依次弹出节点，先将右子树入栈，再将左子树入栈。中序遍历和后序遍历类似，只是在弹出节点时输出。

时间复杂度

遍历每个节点，时间复杂度为O(n)。

Python 代码

n = int(input())
tree = {}
for i in range(n):
    fa, lch, rch = map(int, input().split())
    tree[fa] = (lch, rch)

def preorder(node):
    stack = [node]
    res = []
    while stack:
        node = stack.pop()
        if node == -1:
            continue
        res.append(node)
        stack.append(tree[node][1])
        stack.append(tree[node][0])
    return res

def inorder(node):
    stack = []
    res = []
    while stack or node != -1:
        if node != -1:
            stack.append(node)
            node = tree[node][0]
        else:
            node = stack.pop()
            res.append(node)
            node = tree[node][1]
    return res

def postorder(node):
    stack = [(node, False)]
    res = []
    while stack:
        node, visited = stack.pop()
        if node == -1:
            continue
        if visited:
            res.append(node)
        else:
            stack.append((node, True))
            stack.append((tree[node][1], False))
            stack.append((tree[node][0], False))
    return res

print(' '.join(map(str, preorder(1))))
print(' '.join(map(str, inorder(1))))
print(' '.join(map(str, postorder(1))))