二叉树的递归遍历和非递归遍历

二叉树的递归遍历：

1. 前序遍历：先遍历根节点，再遍历左子树，最后遍历右子树。

   def preorderTraversal(root):
       if not root:
           return []
       res = [root.val]
       res += preorderTraversal(root.left)
       res += preorderTraversal(root.right)
       return res

2. 中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。

   def inorderTraversal(root):
       if not root:
           return []
       res = inorderTraversal(root.left)
       res += [root.val]
       res += inorderTraversal(root.right)
       return res

3. 后序遍历：先遍历左子树，再遍历右子树，最后遍历根节点。

   def postorderTraversal(root):
       if not root:
           return []
       res = postorderTraversal(root.left)
       res += postorderTraversal(root.right)
       res += [root.val]
       return res

二叉树的非递归遍历：

1. 前序遍历：

   def preorderTraversal(root):
       if not root:
           return []
       res = []
       stack = [root]
       while stack:
           node = stack.pop()
           res.append(node.val)
           if node.right:
               stack.append(node.right)
           if node.left:
               stack.append(node.left)
       return res

2. 中序遍历：

   def inorderTraversal(root):
       if not root:
           return []
       res = []
       stack = []
       node = root
       while node or stack:
           while node:
               stack.append(node)
               node = node.left
           node = stack.pop()
           res.append(node.val)
           node = node.right
       return res

3. 后序遍历：

   def postorderTraversal(root):
       if not root:
           return []
       res = []
       stack = [root]
       while stack:
           node = stack.pop()
           if node.left:
               stack.append(node.left)
           if node.right:
               stack.append(node.right)
           res.append(node.val)
       return res[::-1]