二叉树遍历

二叉树的遍历是二叉树操作中的一个基本且重要的概念，它指的是按照一定的规则访问二叉树中的每个节点，并且每个节点仅被访问一次。常见的二叉树遍历方式有四种：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）。

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。对于每个节点，都遵循这个顺序进行遍历。

• 递归实现：

  void preorderTraversal(TreeNode root) {  if (root == null) return;  System.out.print(root.val + " "); // 访问根节点  preorderTraversal(root.left); // 遍历左子树  preorderTraversal(root.right); // 遍历右子树  
  }

• 非递归（迭代）实现（使用栈）：

  void preorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  if (root != null) stack.push(root);  while (!stack.isEmpty()) {  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);  }  
  }

  2. 中序遍历（In-order Traversal）

  中序遍历的顺序是：左子树 -> 根节点 -> 右子树。这常用于二叉搜索树（BST）中，因为这样可以得到一个有序的节点序列。

• 递归实现

  void inorderTraversal(TreeNode root) {  if (root == null) return;  inorderTraversal(root.left); // 遍历左子树  System.out.print(root.val + " "); // 访问根节点  inorderTraversal(root.right); // 遍历右子树  
  }

• 非递归（迭代）实现（使用栈）：

  void inorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  TreeNode curr = root;  while (curr != null || !stack.isEmpty()) {  while (curr != null) {  stack.push(curr);  curr = curr.left; // 遍历到最左节点  }  curr = stack.pop(); // 弹出栈顶元素  System.out.print(curr.val + " "); // 访问节点  curr = curr.right; // 转向右子树  }  
  }

  3. 后序遍历（Post-order Traversal）

  后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

• 递归实现：

  void postorderTraversal(TreeNode root) {  if (root == null) return;  postorderTraversal(root.left); // 遍历左子树  postorderTraversal(root.right); // 遍历右子树  System.out.print(root.val + " "); // 访问根节点  
  }

• 非递归（迭代）实现（使用栈）：

  void postorderTraversalIterative(TreeNode root) {  Stack<TreeNode> stack = new Stack<>();  TreeNode prev = null; // 用于记录上一次访问的节点  while (root != null || !stack.isEmpty()) {  while (root != null) {  stack.push(root);  root = root.left; // 遍历到最左节点  }  root = stack.peek(); // 弹出栈顶元素但不移除  // 如果右子树为空或者右子树已经访问过，则访问当前节点  if (root.right == null || root.right == prev) {  stack.pop();  System.out.print(root.val + " "); // 访问节点  prev = root;  root = null; // 回到上层循环，检查是否有其他节点需要访问  } else {  root = root.right; // 否则，转向右子树  }  }  
  }

  4. 层序遍历

• 非递归（迭代）实现（使用队列）

  import java.util.LinkedList;  
  import java.util.Queue;  class TreeNode {  int val;  TreeNode left;  TreeNode right;  TreeNode(int x) { val = x; }  
  }  public class BinaryTreeLevelOrderTraversal {  public void levelOrderTraversal(TreeNode root) {  if (root == null) return;  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root); // 将根节点加入队列  while (!queue.isEmpty()) {  TreeNode currentNode = queue.poll(); // 从队列中取出一个节点  System.out.print(currentNode.val + " "); // 访问该节点  // 如果左子节点不为空，则将其加入队列  if (currentNode.left != null) {  queue.offer(currentNode.left);  }  // 如果右子节点不为空，则将其加入队列  if (currentNode.right != null) {  queue.offer(currentNode.right);  }  }  }  
  }

• 非递归（迭代）实现

• 实际上，层序遍历不常使用递归实现，因为递归本质上是栈的操作，而层序遍历需要的是队列。但我们可以借助一些额外的数据结构（如数组或链表）来模拟层序遍历的效果，但这通常不是推荐的做法，因为它违背了层序遍历的本意。