二叉树生成与遍历

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

def create_tree(data: list):
    if not data:
        return None
    first_node = Node(data[0])
    tmp_list = [first_node]
    tmp_count = 0
    for item in data[1:]:
        node = tmp_list[0]
        new_node = Node(item) if item is not None else None
        if tmp_count == 0:
            node.left = new_node
            # add to tmp_list
            if item is not None:
                tmp_list.append(new_node)
            tmp_count += 1
            continue
        if tmp_count == 1:
            node.right = new_node
            if item is not None:
                tmp_list.append(new_node)
            # POP
            tmp_list.pop(0)
            tmp_count = 0
            continue
    return first_node

def pre_order_traversal(tree: Node):
    ret = []

    def innner(node):
        if node is None:
            return
        ret.append(node.val)
        innner(node.left)
        innner(node.right)

    innner(tree)
    return ret


def in_order_traversal_with_loop(tree: Node):
    ret = []
    # stack
    tmp_list = [tree]
    passed_node = []
    while True:
        if not tmp_list:
            break
        node = tmp_list[-1]
        if node.left is not None and node not in passed_node:
            passed_node.append(node)
            tmp_list.append(node.left)
            continue
        # 出
        node = tmp_list.pop()
        ret.append(node.val)
        if node.right is not None:
            # 压
            tmp_list.append(node.right)

    return ret


def in_order_traversal(tree: Node):
    ret = []

    def innner(node):
        if node is None:
            return
        innner(node.left)
        ret.append(node.val)
        innner(node.right)

    innner(tree)
    return ret


def post_order_traversal(tree: Node):
    ret = []

    def innner(node):
        if node is None:
            return
        innner(node.left)
        innner(node.right)
        ret.append(node.val)

    innner(tree)
    return ret


if __name__ == '__main__':
    data = list(range(10))
    tree = create_tree(data)
    print(tree)
    print(pre_order_traversal(tree))
    print(in_order_traversal(tree))
    print(pre_order_traversal_with_loop(tree))

#         0
#     1       2
#  3    4    5  6
# 7 8  9