7-2. 二叉树的前序、中序、后序遍历及层次遍历的非递归实现

前序、中序、后序遍历的非递归实现均需要借助栈，层次遍历需要借助队列。

# 定义树节点
class treeNode(object):
    def __init__(self, x, lchild=None, rchild=None):
        self.val = x
        self.lchild = lchild
        self.rchild = rchild
        
# 前序遍历非递归实现
def pre_order_traversal(root):
    res, stack = [], []
    node = root
    while node or stack:
        while node:
            res.append(node.val)
            stack.append(node)
            node = node.lchild
        node = stack.pop()
        node = node.rchild
    return res

# 中序遍历非递归实现
def in_order_traversal(root):
    res, stack = [], []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.lchild
        node = stack.pop()
        res.append(node.val)
        node = node.rchild
    return res

# 后序遍历非递归实现
def post_order_traversal(root):
    res, stack = [], []
    node = root
    stack.append(node)
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.lchild:
            stack.append(node.lchild)
        if node.rchild:
            stack.append(node.rchild)
    return res[::-1]

# 层次遍历/广度优先遍历(BFS)
def broad_first_search(root):
    from collections import deque
    queue = deque([root])
    res = []
    while queue:
        node = queue.popleft()
        if node:
            res.append(node.val)
            queue.append(node.lchild)
            queue.append(node.rchild)
    return res