二叉树算法之二叉树遍历（前序、中序、后序、层次遍历）

二叉树遍历是指按照某种顺序访问二叉树的所有节点。常见的二叉树遍历方式包括前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）和层次遍历（Level-order Traversal）。不同的遍历方式有不同的应用场景，下面我们详细介绍这几种遍历方式及其实现。

1. 前序遍历（Preorder Traversal）

在前序遍历中，按照“根节点 -> 左子树 -> 右子树”的顺序遍历二叉树的节点。即：首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

前序遍历的顺序：

当前节点 -> 左子节点 -> 右子节点

前序遍历的递归实现：

// 定义二叉树节点
class TreeNode {int val;TreeNode left, right;TreeNode(int val) {this.val = val;this.left = this.right = null;}
}public class BinaryTreeTraversal {// 前序遍历 - 递归实现public void preorder(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " ");  // 访问根节点preorder(root.left);  // 递归遍历左子树preorder(root.right);  // 递归遍历右子树}
}

前序遍历的非递归实现：

可以用栈模拟递归的过程，先访问根节点，然后将右子树和左子树依次压栈，确保左子树先被遍历。

import java.util.Stack;public class BinaryTreeTraversal {// 前序遍历 - 非递归实现public void preorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();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. 中序遍历（Inorder Traversal）

在中序遍历中，按照“左子树 -> 根节点 -> 右子树”的顺序遍历二叉树的节点。即：首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

中序遍历的顺序：

左子节点 -> 当前节点 -> 右子节点

中序遍历的递归实现：

public class BinaryTreeTraversal {// 中序遍历 - 递归实现public void inorder(TreeNode root) {if (root == null) {return;}inorder(root.left);  // 递归遍历左子树System.out.print(root.val + " ");  // 访问根节点inorder(root.right);  // 递归遍历右子树}
}

中序遍历的非递归实现：

同样可以使用栈来实现，先遍历到最左边的节点，然后逐步回溯访问根节点，最后遍历右子树。

import java.util.Stack;public class BinaryTreeTraversal {// 中序遍历 - 非递归实现public void inorderIterative(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. 后序遍历（Postorder Traversal）

在后序遍历中，按照“左子树 -> 右子树 -> 根节点”的顺序遍历二叉树的节点。即：首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

后序遍历的顺序：

左子节点 -> 右子节点 -> 当前节点

后序遍历的递归实现：

public class BinaryTreeTraversal {// 后序遍历 - 递归实现public void postorder(TreeNode root) {if (root == null) {return;}postorder(root.left);  // 递归遍历左子树postorder(root.right);  // 递归遍历右子树System.out.print(root.val + " ");  // 访问根节点}
}

后序遍历的非递归实现：

后序遍历较复杂，需要两个栈，一个用于模拟递归，另一个用于输出结果。

import java.util.Stack;public class BinaryTreeTraversal {// 后序遍历 - 非递归实现public void postorderIterative(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();Stack<TreeNode> output = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();output.push(node);if (node.left != null) {stack.push(node.left);  // 左子树入栈}if (node.right != null) {stack.push(node.right);  // 右子树入栈}}while (!output.isEmpty()) {System.out.print(output.pop().val + " ");  // 输出结果}}
}

4. 层次遍历（Level-order Traversal）

层次遍历是按照每一层节点的顺序从上到下，从左到右依次遍历二叉树的节点。可以通过队列实现，每次从队列中取出一个节点，然后将其左右子节点依次加入队列。

层次遍历的顺序：

按照从上到下、从左到右的层次顺序遍历节点

层次遍历的实现：

import java.util.LinkedList;
import java.util.Queue;public class BinaryTreeTraversal {// 层次遍历 - 使用队列实现public void levelOrder(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");  // 访问当前节点if (node.left != null) {queue.offer(node.left);  // 左子节点入队}if (node.right != null) {queue.offer(node.right);  // 右子节点入队}}}
}