1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
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