二叉树的遍历递归法和环线法
二叉树的遍历有三种常见的方式：前序遍历、中序遍历和后序遍历。下面分别介绍二叉树的遍历的递归法和非递归法（环线法）。
1. 前序遍历：
  - 递归法：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。
  ```python
  def preorderTraversal(root):
      if not root:
          return []
      return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
  ```
  - 环线法：使用一个栈，先将根节点入栈，然后弹出栈顶元素并访问，接着先将右子节点入栈，再将左子节点入栈。重复这个过程直到栈为空。
  ```python
  def preorderTraversal(root):
      if not root:
          return []
      stack = [root]
      res = []
      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. 中序遍历：
  - 递归法：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
  ```python
  def inorderTraversal(root):
      if not root:
          return []
      return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
  ```
  - 环线法：使用一个栈，将当前节点及其所有左子节点依次入栈。当栈不为空时，弹出栈顶元素并访问，然后将当前节点指向弹出节点的右子节点，之后继续将当前节点及其所有左子节点入栈。
  ```python
  def inorderTraversal(root):
      if not root:
          return []
      stack = []
      res = []
      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. 后序遍历：
  - 递归法：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。
  ```python
  def postorderTraversal(root):
      if not root:
          return []先序中序后序遍历二叉树
      return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]
  ```
  - 环线法：使用一个栈，将根节点入栈。然后定义一个变量prev，用于记录上一次访问的节点。重复以下步骤，直到栈为空：
    - 取出栈顶元素，如果栈顶元素的右子节点为空或者已经访问过，则访问该节点，并将其
赋给prev变量。否则，将栈顶元素的右子节点和自身依次入栈。
  ```python
  def postorderTraversal(root):
      if not root:
          return []
      stack = [root]
      res = []
      prev = None
      while stack:
          node = stack[-1]
          if (not node.left and not node.right) or (prev and (prev == node.left or prev == node.right)):
              res.append(node.val)
              prev = stack.pop()
          else:
              if node.right:
                  stack.append(node.right)
              if node.left:
                  stack.append(node.left)
      return res
  ```
希望对你有所帮助！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。