Python中的树遍历算法

# 定义树节点类
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 前序遍历
def preorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

# 中序遍历
def inorderTraversal(root):
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        node = stack.pop()
        res.append(node.val)
        root = node.right
    return res

# 后序遍历
def postorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

# 测试样例
root = TreeNode('p')
root.left = TreeNode('i')
root.right = TreeNode('d')
root.left.left = TreeNode('a')
root.left.right = TreeNode('n')
root.right.left = TreeNode('a')
root.right.right = TreeNode('c')
print(preorderTraversal(root)) # ['p', 'i', 'a', 'n', 'd', 'a', 'c']
print(inorderTraversal(root)) # ['a', 'i', 'n', 'p', 'a', 'd', 'c']
print(postorderTraversal(root)) # ['a', 'n', 'i', 'c', 'a', 'd', 'p']