二叉树运算和非递归遍历

二叉树是一种重要的数据结构，它的遍历方式有递归和非递归两种。下面将分别介绍二叉树的基本运算和非递归遍历算法。

1. 二叉树的基本运算
建立二叉树的三叉链式存储结构，可以通过以下步骤完成二叉树的基本运算：
- 从键盘上输入二叉树的各个结点，建立三叉链表
- 输出该二叉树
- 递归的先序遍历、中序遍历、后序遍历算法
- 非递归的先序遍历、中序遍历、后序遍历算法
- 非递归的层次遍历算法

2. 非递归遍历算法
非递归遍历算法主要引入了堆栈和队列的思想，下面分别介绍非递归的先序遍历、中序遍历、后序遍历和层次遍历算法。
- 非递归的先序遍历算法：

  def preorderTraversal(root):
      if not root:
          return []
      stack, res = [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

- 非递归的中序遍历算法：

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

- 非递归的后序遍历算法：

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

- 非递归的层次遍历算法：

  def levelOrder(root):
      if not root:
          return []
      queue, res = [root], []
      while queue:
          level = []
          for i 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