二叉树遍历

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

class (object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def preorder(root):
            if root:
                self.result.append(root.val)
                preorder(root.left)
                preorder(root.right)       
        preorder(root)
        return self.result

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

class (object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def preorder(root):
            cur, stack = root, []
            while cur or stack:
                while cur:
                    self.result.append(cur.val)
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                cur = cur.right
        preorder(root)
        return self.result

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

class (object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def inorder(root):
            if root:
                inorder(root.left)
                self.result.append(root.val)
                inorder(root.right)
        inorder(root)
        return self.result

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

class (object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def inorder(root):
            cur, stack = root, []
            while cur or stack:
                while cur:
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                self.result.append(cur.val)
                cur = cur.right
        inorder(root)
        return self.result

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

class (object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def postorder(root):
            if root:
                postorder(root.left)
                postorder(root.right)
                self.result.append(root.val)
        postorder(root)
        return self.result

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

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def postorder(root):
            if not root:
                return None
            else:
                stack_first = [root]
                stack_second = []
                while stack_first:
                    cur = stack_first.pop()
                    if cur.left:
                        stack_first.append(cur.left)
                    if cur.right:
                        stack_first.append(cur.right)
                    stack_second.append(cur)
                while stack_second:
                    self.result.append(stack_second.pop().val)
                return self.result
        postorder(root)
        return self.result

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

class Solution(object):
    def levelTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.result = []
        def levelorder(root):
            if root:
                queue = [root]
                while queue:
                    cur = queue.pop(0)
                    self.result.append(cur.val)
                    if cur.left:
                        queue.append(cur.left)
                    if cur.right:
                        queue.append(cur.right)
                return self.result
        levelorder(root)
        return self.result