python实现二叉树的前序遍历、中序遍历、后序遍历和层序遍历（递归和非递归实现）

前序遍历（递归）

class Solution:
    def preorder(self,root):
        if not root:
            return []
        return [root.val] + [self.preorder(root.left)] + [self.preorder(root.right)]

中序遍历（递归）

class Solution:
    def middleorder(self,root):
        if not root:
            return []
        return [self.middleorder(root.left)] + [root.val] + [self.middleorder(root.right)]

后序遍历（递归）

class Solution:
    def postorder(self,root):
        if not root:
            return []
        return [self.postorder(root.left)] + [self.postorder(root.right)]+[root.val]

前序遍历（非递归）

class Solution:
    def preorder(self,root):
        if root is None:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node is not None:
                res.append(node.val)
                if node.right is not None:
                    stack.append(node.right)
                if node.left id not None:
                    stack.append(node.left)
        return res

中序遍历（非递归）

class Solution:
    def middleorder(self,root):
        res = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root= stack.pop()
            res.append(root.val)
            root = root.right
        return res

层序遍历（非递归）

class Solution:
    def levelorder(self,root):
        if root is None:
            return []
        res = []
        queue= [root]
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            res.append(level)
        return res