class NodeClass:
    def __init__(self, element):
        self.element = element
        self.left = None
        self.right = None

returnPreList = []
def pre_digui(root): # 前序遍历 递归
    if root:
        returnPreList.append(root.element)
        pre_digui(root.left)
        pre_digui(root.right)

def pre_duizhan(root): # 前序 堆栈
    returnList = []
    nodeList = []
    node = root
    while nodeList or node:
        while node:
            nodeList.append(node)
            returnList.append(node.element)
            node = node.left
        node = nodeList.pop()
        node = node.right
    print(returnList)

returnMidList = []
def mid_digui(root): # 中序递归
    if root:
        mid_digui(root.left)
        returnMidList.append(root.element)
        mid_digui(root.right)

def mid_duizhan(root): # 中序堆栈
    returnList = []
    nodeList = []
    node = root
    while nodeList or node:
        while node:
            nodeList.append(node)
            node = node.left
        node = nodeList.pop()
        returnList.append(node.element)
        node = node.right
    print(returnList)

returnPostList = []
def post_digui(root): # 后序递归
    if root:
        post_digui(root.left)
        post_digui(root.right)
        returnPostList.append(root.element)

def post_duizhan(root): # 后序堆栈
    returnList = []
    tempList = [root]
    while tempList:
        temp = tempList.pop()
        if type(temp) is NodeClass:
            tempList.append(temp.element)
            if temp.right:
                tempList.append(temp.right)
            if temp.left:
                tempList.append(temp.left)
        else:
            returnList.append(temp)
    print(returnList)


def post_duizhan2(root): # 后序堆栈方法2
    returnList = []
    nodeList1 = [root]
    nodeList2 = []
    while nodeList1:
        node = nodeList1.pop()
        nodeList2.append(node)
        if node.left:
            nodeList1.append(node.left)
        if node.right:
            nodeList1.append(node.right)
    while nodeList2:
        returnList.append(nodeList2.pop().element)
    print(returnList)

root = NodeClass(0)
root.left = NodeClass(1)
root.right = NodeClass(2)
root.left.left = NodeClass(3)
root.left.right = NodeClass(4)
root.right.left = NodeClass(5)
root.right.right = NodeClass(6)



# pre_digui(root)
# print(returnPreList)
# pre_duizhan(root)

# mid_digui(root)
# print(returnMidList)
# mid_duizhan(root)

post_digui(root)
print(returnPostList)
post_duizhan(root)
post_duizhan2(root)