2.遍历查找

作用：

• 用于树、图的遍历

广度优先：

• 广度优先遍历通常借助队列来实现。队列遵循先进先出的规则，而广度优先遍历则遵循逐层推进的规则
• 代码实现（树）：

  /* 层序遍历 */
  func levelOrder(root *TreeNode) []any {
      // 初始化队列，加入根节点
      queue := list.New()
      queue.PushBack(root)
      // 初始化一个切片，用于保存遍历序列
      nums := make([]any, 0)
      for queue.Len() > 0 {
          // 队列出队
          node := queue.Remove(queue.Front()).(*TreeNode)
          // 保存节点值
          nums = append(nums, node.Val)
          if node.Left != nil {
              // 左子节点入队
              queue.PushBack(node.Left)
          }
          if node.Right != nil {
              // 右子节点入队
              queue.PushBack(node.Right)
          }
      }
      return nums
  }

深度优先：

• 深度优先遍历通常借助栈/递归来实现。递归`先"递"后"归"的过程，根深度优先遍历“先走到尽头，再回溯继续”思想一致。
• 树的深度优先遍历，根据根在左节点、右节点的先中后顺序，分别对应前序遍历、中序遍历和后序遍历。
• 二叉搜索树因为左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值的特性，使用中序遍历即可得到升序结果
• 代码实现：

  /* 前序遍历 */
  func preOrder(node *TreeNode) {
      if node == nil {
          return
      }
      // 访问优先级：根节点 -> 左子树 -> 右子树
      nums = append(nums, node.Val)
      preOrder(node.Left)
      preOrder(node.Right)
  }
  
  /* 中序遍历 */
  func inOrder(node *TreeNode) {
      if node == nil {
          return
      }
      // 访问优先级：左子树 -> 根节点 -> 右子树
      inOrder(node.Left)
      nums = append(nums, node.Val)
      inOrder(node.Right)
  }
  
  /* 后序遍历 */
  func postOrder(node *TreeNode) {
      if node == nil {
          return
      }
      // 访问优先级：左子树 -> 右子树 -> 根节点
      postOrder(node.Left)
      postOrder(node.Right)
      nums = append(nums, node.Val)
  }