树的遍历算法的python实现

def inorder(root):
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]
    res = inorder(root.left)
    res.append(root.val)
    res += inorder(root.right)
    return res

def preorder(root):
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]
    res = [root.val]
    res += preorder(root.left)
    res += preorder(root.right)
    return res

def postorder(root):
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]
    res = postorder(root.left)
    res += postorder(root.right)
    res.append(root.val)
    return res

def inorder(root):
    stack, res = [root], []
    visited = {}
    while stack:
        if stack[-1].left and stack[-1] not in visited:
            visited[stack[-1]] = 1
            stack.append(stack[-1].left)
        else:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
    return res

def preorder(root):
    stack, res = [root], []
    visited = {}
    while stack:
        if stack[-1] not in visited:
            res.append(stack[-1].val)
        if stack[-1].left and stack[-1] not in visited:
            visited[stack[-1]] = 1
            stack.append(stack[-1].left)
        else:
            node = stack.pop()
            if node.right:
                stack.append(node.right)
    return res

def postorder(root):
    stack, res = [root], []
    visited = {}
    while stack:
        if stack[-1].left and stack[-1] not in visited:
            visited[stack[-1]] = 1
            stack.append(stack[-1].left)
        elif stack[-1].right and (stack[-1] not in visited or visited[stack[-1]] != 2):
            visited[stack[-1]] = 2
            stack.append(stack[-1].right)
        else:
            res.append(stack[-1].val)
            stack.pop()
    return res