class Tree():

    def __init__(self, root = root):
        self.root = root

    # 前序遍历非递归实现
    def preorder_no_recursion(self, root):
        stack = []
        res = []
        stack.push((root, False))
        while stack:
            root, visited = stack.pop()
            if not root:
                continue
            if visited:
                res.append(root.val)
            else:
                stack.append((root.right, False))
                stack.append(root.left, False)
                stack.append(root, True)
        return res

    # 上述版本的简化版
    def preorder_simplify(self, root):
        stack = []
        res = []
        stack.push(root)
        while stack:
            root = stack.pop()
            if not root:
                continue
            res.append(root.val)
            stack.append(root.right)
            stack.append(root.left)

    # 前序遍历递归实现
    def preorder_recursion(self, root):
        self.res = []
        def helper(root):
            if not root:
                return
            self.res.append(root.val)
            helper(root.left)
            helper(root.right)
        helper(root)
        return self.res

class Tree():

    def __init__(self, root = root):
        self.root = root

    # 中序遍历非递归实现
    def inorder_no_recursion(self, root):
        stack = []
        res = []
        stack.append((root, False))
        while stack:
            root, visited = stack.pop()
            if not root:
                continue
            if visited:
                res.append(root.val)
            else:
                res.append((root.right, False))
                res.append((root, True))
                res.append((root.left, False))
        return res
        
    # 中序遍历另一种易实现版本
    def inorder_no_recursion(self, root):
        stack = []
        res = []
        while stack or root:
            # if root is not Null, push it to stack
            while root:
                stack.append(root)
                root = root.left
            # the pop is always not Null
            root = stack.pop()
            val = root.val
            res.append(val)
            root = root.right

    # 中序遍历递归实现
    def inorder_recursion(self, root):
        self.res = []
        def helper(root):
            if not root:
                return
            helper(root.left)
            self.res.append(root.val)
            helper(root.right)
        helper(root)
        return self.res

class Tree():

    def __init__(self, root = root):
        self.root = root


    # 后序遍历非递归实现
    def postorder_no_recursion(self, root):
        stack = []
        res = []
        stack.push((root, False))
        while stack:
            root, visited = stack.pop()
            if not root:
                continue
            if visited:
                res.append(root.val)
            else:
                stack.append(root, True)
                stack.append((root.right, False))
                stack.append(root.left, False)
        return res

    # 后续遍历递归实现
    def postorder_recursion(self, root):
        self.res = []
        def helper(root):
            if not root:
                return
            helper(root.left)
            helper(root.right)
            self.res.append(root.val)
        helper(root)