二叉树的前序遍历
给定一个二叉树，返回它的前序遍历
示例:
思路
前序遍历1.先访问根节点，把元素加入到List中；
2.递归遍历左子树，把左子树的遍历结果加入到List中；
3.递归遍历右子树，把右子树的遍历结果加入到List中。
4.返回
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
在计算机科学中，二叉树是一种特殊的图结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树遍历是针对二叉树进行操作的一种基本算法，主要有三种类型：前序遍历、中序遍历和后序遍历。本问题主要关注的是前序遍历，它是二叉树遍历的一种常见方式。
**前序遍历**的顺序是：先访问根节点，然后递归地遍历左子树，最后遍历右子树。这是一个深度优先搜索（DFS）策略。对于给定的题目，我们需要编写一个Java程序来实现二叉树的前序遍历，并返回一个包含所有节点值的列表。
在Java中，我们可以定义一个`TreeNode`类来表示二叉树的节点，如下所示：
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
```
接下来，我们需要创建一个解决方案类`Solution`，其中包含一个名为`preorderTraversal`的方法，该方法接受一个`TreeNode`类型的参数`root`，表示二叉树的根节点。这个方法会返回一个`List<Integer>`，包含按前序遍历顺序排列的节点值。
在`preorderTraversal`方法内部，我们首先初始化一个空的ArrayList `res`来存储遍历结果。如果输入的根节点为null，表示没有树可遍历，因此直接返回空列表。否则，按照前序遍历的顺序进行操作：
1. 访问根节点，将其值添加到结果列表`res`中。
2. 递归地遍历左子树，将左子树的前序遍历结果通过`addAll`方法合并到`res`中。
3. 递归地遍历右子树，将右子树的前序遍历结果同样合并到`res`中。
最终返回结果列表`res`。
以下是完整的`Solution`类代码：
```java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 先访问根节点
res.add(root.val);
// 递归遍历左子树
res.addAll(preorderTraversal(root.left));
// 递归遍历右子树
res.addAll(preorderTraversal(root.right));
return res;
}
}
```
在这个解决方案中，`addAll`方法用于将一个集合的所有元素添加到另一个集合的末尾，这使得我们可以方便地将左子树和右子树的遍历结果合并到主结果列表中。这个方法是Java集合框架的一部分，是`List`接口的一个方法，它可以在不改变原有列表大小的情况下添加多个元素。
二叉树的前序遍历是一个基础但重要的概念，适用于多种场景，例如数据结构的序列化、搜索和复制等。通过递归的方式，我们可以轻松地实现这一遍历策略，并用Java代码将其表达出来。
- 1
- 2
前往页