本文共 1811 字，大约阅读时间需要 6 分钟。

递归

先序遍历--根左右

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

中序遍历-左根右

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

 后序遍历-左右根

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

非递归

先序遍历

def preOrder(root):    stack = [root]    while stack : #len(stack ) > 0        print(root.val)        if root.right :  #最后遍历所以先放进去            stack.append(root.right)        if root.left :            stack.append(root.left)        root= stack.pop()

中序遍历

def inOrder(root):    stack = []    p= root    while p or stack: #p is not None or len(stack) > 0        if p:            stack.append(p)            p= p.left #不断向左深入        else:            p= stack.pop()            print(p.val)            p= p.right #根遍历后向右

后序遍历

# 使用两个栈结构# 第一个栈进栈顺序：先序遍历跟->左->右  # 第二个栈=第一个栈pop顺序： 跟->右->左# 最后第二个栈依次出栈 左->右->跟def postOrder(root):    stack = [root]    stack2 = []    while len(stack) > 0:        root= stack.pop() #根先弹出        stack2.append(root)        if root.left:#左边最后弹出            stack.append(root.left)        if root.right :            stack.append(root.right)    while stack2: #len(stack2) > 0:        print(stack2.pop().val)

层次遍历

def levelOrder( root) :        #先遍历后面再返回 一个节点 一个存储  一个temp        if not root:return []        res=[]        nodeLayer=[root]        while nodeLayer:            tempval=[] #存储值            tempNode=[] #存储节点            for node in nodeLayer: #每层的值和节点更新                tempval.append(node.val)                if node.left:tempNode.append(node.left)                if node.right:tempNode.append(node.right)            nodeLayer=tempNode            res.append(tempval)        return res

转载地址：http://qlhdi.baihongyu.com/