二叉树 前序 中序 后序遍历的递归，非递归Python实现

前言

马上网易游戏面试，为了不重蹈覆辙，最近复习了下二叉树 前序 中序 后序遍历的递归和非递归的Python实现方法。在这里做个记录。

代码

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


# 前序 递归
def pre_order_recur(root):
    if not root:
        return
    print(root.val)
    pre_order_recur(root.left)
    pre_order_recur(root.right)


# 中序 递归
def in_order_recur(root):
    if not root:
        return
    in_order_recur(root.left)
    print(root.val)
    in_order_recur(root.right)


# 后序 递归
def post_order_recur(root):
    if not root:
        return
    post_order_recur(root.left)
    post_order_recur(root.right)
    print(root.val)


# 前序 非递归
def pre_order_none_recur(root):
    if not root:
        return
    stack = [root]
    while stack:
        cur = stack.pop()
        print(cur.val)
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)


# 中序 非递归
def in_order_none_recur(root):
    if not root:
        return
    stack = []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            print(root.val)
            root = root.right


# 后序 非递归
def post_order_none_recur(root):
    if not root:
        return
    stack = []
    mark_node = None
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        elif stack[-1].right != mark_node:
            root = stack[-1].right
            mark_node = None
        else:
            mark_node = stack.pop()
            print(mark_node.val)


if __name__ == '__main__':
    root = Node(1, Node(2, Node(4), Node(5, Node(7))), Node(3, Node(6)))
    print('前序递归的结果：'), pre_order_recur(root)
    print('前序非递归的结果：'), pre_order_none_recur(root)
    print('中序递归的结果：'), in_order_recur(root)
    print('中序非递归的结果：'), in_order_none_recur(root)
    print('后序递归的结果：'), post_order_recur(root)
    print('后序非递归的结果：'), post_order_none_recur(root)

测试用二叉树的结构

运行结果

Github地址

代码文件