题目：144. 二叉树的前序遍历
如果您已经有思路了，或者是N刷了，可以先自己写一遍。
题目分析
要求对一棵二叉树进行前序遍历并返回遍历结果的列表。前序遍历的顺序是先访问根节点，然后访问左子树，最后访问右子树。这种遍历方式主要用于创建一个与原树结构相同的拷贝，因为它先处理节点本身，然后递归地处理子节点。
解题思路
对二叉树进行前序遍历同样可以采用递归或迭代的方式。递归是最直观的方法，但在深度较大的树上可能会遇到栈溢出问题。迭代方法通常使用栈来实现。
- 递归方法：直接按照前序遍历的定义，先处理当前节点，然后递归地遍历左子树和右子树。
- 迭代方法：使用栈来模拟递归过程，手动控制访问的顺序，栈先进后出的特性刚好可以用来实现前序遍历。
Java解法
递归解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
res.add(node.val);
preorder(node.left, res);
preorder(node.right, res);
}
}
|
迭代解法，稍微有点难懂：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
res.add(node.val);
preorder(node.left, res);
preorder(node.right, res);
}
}
|
时间复杂度
O(n)，其中 n 是树中节点的数量。无论是递归还是迭代方法，每个节点都只访问一次。
空间复杂度
递归方法的空间复杂度主要由递归栈的深度决定，最坏情况下为 O(n)，在平衡树中为 O(log n)。
迭代方法的空间复杂度同样依赖于栈的使用，理论上最坏情况下也为 O(n)，在平衡树中为 O(log n)。
References
