두 갈래 트리 찾기 알고리즘

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorder(root:TreeNode):
    """ ， """
    if root == None:
        return
    else:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

def inorder(root:TreeNode):
    """ ， """
    if root == None:
        return
    else:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

def postorder(root:TreeNode):
    """ ， """
    if root == None:
        return
    else:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

def levelorder(root:TreeNode):
    """ ， """
    level=0
    while printLevel(root,level):
        level +=1

def printLevel(root:TreeNode, level):
    """ ， ， """
    if root==None or level<0:
        return False
    elif level == 0:
        print(root.val)
        return True
    else:
        return printLevel(root.left, level-1) + printLevel(root.right, level-1)

def preorderWithStack(root:TreeNode):
    """ ， """
    stack = []
    pnode = root

    while pnode or len(stack)>0:
        while pnode:
            print(pnode)
            stack.append(pnode)
            pnode = pnode.left
        if len(stack)>0:
            pnode = stack.pop().right

def inorderWithStack(root:TreeNode):
    """ ， """
    stack =[]
    pnode = root
    while pnode or len(stack)>0:
        while pnode:
            stack.append(pnode)
            pnode = pnode.left
        if len(stack)>0:
            top = stack.pop()
            print(top.val)
            pnode = top.right

def postorderWithStack(root:TreeNode):
    """ ， ， """
    stack = []
    pnode = root
    stack.append(pnode)
    while len(stack)>0:
        top = stack[:-1]
        if (not pnode.right and not pnode.left) \
                or (pre and (pre==pnode.left or pre==pnode.right)):
            print(top.val)
            pre = stack.pop()

        if pnode.right:
            stack.append(pnode.right)
        if pnode.left:
            stack.append(pnode.left)

def levelorderWithStack(root:TreeNode):
    """ ， """
    stack=[]
    stack.append(root)
    tempstack = []
    while len(stack)>0:
        for x in stack:
            print(x.val)
            if x.left:
                tempstack.append(x.left)
            if x.right:
                tempstack.append(x.right)
        stack = tempstack
        tempstack=[]