几种遍历的区别

我们知道，一个二叉树有根节点，左节点，左节点。

我们遍历的顺序肯定先是左节点，再右节点。前序、中序、后序的区别就是根节点的位置。

如果根节点在左节点前面，那么就是前序遍历。

如果根节点在两者之间，那么就是中序遍历。对于二叉搜索树而言，中序遍历得到的结果是从小到大的。

如果根节点在右节点后面，那么就是后序遍历了。

对于深度优先，我们对于一棵树，从根节点开始，一直访问左子节点，一直到为空，再向上依次返回访问右子节点。以上面的树结构为例，它访问的顺序为: A,B,D,H,I,E,C,F,J,G。

对于广度优先，我们把树分层，根节点为第一层，根节点的子节点为第二层，第二层的子节点为第三层，依次递推。遍历的时候就对每一层进行依次访问。上面的树结构的遍历结果为：A,B,C,D,E,F,G,H,I,J

代码实现

前序遍历

遍历打印

public void prologuePrint(TreeNode root) {
  if (root == null) {
    return;
  }
  prologuePrint(root.left);
  System.out.print(root.val + " ");
  prologuePrint(root.right);
}

遍历，将数据添加到集合中

public List prologueList(TreeNode root) {
  List result = new ArrayList();
  prologueListHelp(root, result);
  return result;
}

private void prologueListHelp(TreeNode node, List list) {
  if (node == null) {
    return;
  }
  prologueListHelp(node.left, list);
  list.add(node.val);
  prologueListHelp(node.right, list);
}

中序遍历

遍历打印

public void middlePrint(TreeNode root) {
  if (root == null) {
    return;
  }
  middlePrint(root.left);
  System.out.print(root.val + "");
  middlePrint(root.right);
}

遍历将数据添加到集合中

public List middleList(TreeNode root) {
  List result = new ArrayList();
  middleListHelp(root, result);
  return result;
}

private void middleListHelp(TreeNode node, List list) {
  if (node == null) {
    return;
  }
  middleListHelp(node.left, list);
  list.add(node.val);
  middleListHelp(node.right, list);
}

后序遍历

遍历打印

public void postPrint(TreeNode root) {
  if (root == null) {
    return;
  }
  postPrint(root.left);
  System.out.print(root.val + " ");
  postPrint(root.right);
}

遍历将数据添加到集合中

public List postList(TreeNode root) {
  List result = new ArrayList();
  postListHelp(root, result);
  return result;
}

private void postListHelp(TreeNode node, List list) {
  if (node == null) {
    return;
  }
  prologueListHelp(node.left, list);
  list.add(node.val);
  prologueListHelp(node.right, list);
}

深度优先遍历

用栈实现深度优先遍历

public static void DFSPrint(TreeNode root) {
  if (root == null) {
    return;
  }
  Stack<TreeNode> stack = new Stack();
  stack.push(root);
  while (!stack.empty()) {
    TreeNode node = stack.pop();
    System.out.print(node.val + " ");
    //由于栈，先进后出，所以先放右节点
    if (node.right != null) {
      stack.push(node.right);
    }
    if (node.left != null) {
      stack.push(node.left);
    }
  }
}

广度优先遍历

用队列实现广度优先遍历

public static void BFSPrint(TreeNode root) {
  if (root == null) {
    return;
  }
  Queue<TreeNode> queue = new LinkedList();
  queue.add(root);
  while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    System.out.print(node.val + " ");
    //先进先出，先放左节点，再放右节点。遍历的时候就是每一层从左到右的顺序
    if (node.left != null) {
      queue.add(node.left);
    }
    if (node.right != null) {
      queue.add(node.right);
    }
  }
}