算法之二叉树的遍历

TreeNode

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


"""tree
            5
        1       2
    3     4   6    8
9                     11
"""

# 推荐采用这种构造方式，非常直观
root=TreeNode(5,
              TreeNode(1,
                       TreeNode(3,
                                TreeNode(9),
                                None),
                       TreeNode(4)
                       ),
              TreeNode(2,
                       TreeNode(6),
                       TreeNode(8,
                                None,
                                TreeNode(11))
                       )
              )

前序遍历

def preorder(root):
    if not root:return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

中序遍历

def inorder(root):
    if not root:return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

后序遍历

def postorder(root):
    if not root:return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

广度优先（层序遍历）

def bfs(root):
    queue=[root]
    while queue:
        node=queue.pop(0)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        print(node.val)

深度优先

def dfs(root):
    stack=[root]
    while stack:
        node=stack.pop()
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
        print(node.val)

总结

1. 前序、中序、后序遍历其实都是深度优先思想的体现，我这里采用递归写法，便于记忆，三者的区别在于：遍历左右子树与对此节点做出操作（print(root.val)）的顺序

2. 深度优先使用栈，广度优先使用队列，我这里均采用迭代写法；注意深度优先的栈的先入后出特性，应先判断right再判断left