from .binary_tree import TreeNode

"""
二叉树的遍历：层序遍历，一层一层的遍历，方向为从左到右或从右到左
"""


def level_order(root: TreeNode):
    q = [root]
    res = []
    while q:
        node = q.pop(0)
        res.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return res


"""
二叉树遍历：前序、中序、后序遍历，都属于「深度优先遍历 depth-first traversal, DFS」

前序：先遍历根节点，再遍历左节点，再遍历右节点
中续：先遍历左节点，再遍历根节点，再遍历右节点
后续：先左，再右，后中
"""


def pre_order(root: TreeNode):
    # 前序遍历
    print(root.val)
    if root.left:
        pre_order(root.left)
    if root.right:
        pre_order(root.right)


def in_order(root: TreeNode):
    in_order(root.left)
    print(root.val)
    in_order(root.right)


def post_order(root: TreeNode):
    post_order(root.left)
    post_order(root.right)
    print(root.val)