二叉树前序遍历的 Java 实现，包括递归和非递归两种方式
二叉树前序遍历是一种遍历树节点的方式，遵循特定的顺序。其基本过程可以总结为以下几个步骤：
前序遍历的顺序
访问根节点：首先处理当前节点。
递归遍历左子树：然后依次访问左子树。
递归遍历右子树：最后访问右子树。
这种遍历方式的特点是每次都会先处理根节点，再处理左右子树，因此叫做“前序”。
例子
考虑下面的二叉树：
A/ \B C/ \
D E
前序遍历的步骤：
访问根节点 A
递归访问左子树：
访问 B
递归访问 B 的左子树：
访问 D
递归访问 B 的右子树：
访问 E
递归访问右子树：
访问 C
前序遍历的结果：A, B, D, E, C
特点
树的结构：前序遍历能够保存树的结构。通过前序遍历的结果，可以恢复出原来的树形结构。
适用场景：在某些场景下，例如复制树或者进行某些类型的树形操作，前序遍历是非常有效的。
递归与非递归：前序遍历可以通过递归和非递归（使用栈）两种方式实现。
时间复杂度
前序遍历的时间复杂度为 O(n)，其中 n 是树中节点的总数，因为每个节点都要被访问一次。
空间复杂度
递归实现的空间复杂度为 O(h)，h 是树的高度，主要由递归调用栈占用。
非递归实现的空间复杂度也是 O(h)，因为栈中存储的节点数不超过树的高度。
下面是二叉树前序遍历的 Java 实现，包括递归和非递归两种方式。
- 递归实现
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}import java.util.ArrayList;
import java.util.List;public class PreorderTraversal {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traverse(root, result);return result;}private void traverse(TreeNode node, List<Integer> result) {if (node != null) {result.add(node.val); // 访问根节点traverse(node.left, result); // 递归左子树traverse(node.right, result); // 递归右子树}}
}
2. 非递归实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PreorderTraversalIterative {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val); // 访问根节点if (node.right != null) {stack.push(node.right); // 先右后左入栈}if (node.left != null) {stack.push(node.left);}}return result;}
}
示例使用
假设有如下的二叉树：
// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);// 递归遍历
PreorderTraversal pt = new PreorderTraversal();
List<Integer> result = pt.preorderTraversal(root);
System.out.println(result); // 输出: [1, 2, 4, 5, 3]// 非递归遍历
PreorderTraversalIterative pti = new PreorderTraversalIterative();
List<Integer> resultIterative = pti.preorderTraversal(root);
System.out.println(resultIterative); // 输出: [1, 2, 4, 5, 3]