1，问题描述
144. 二叉树的前序遍历
难度：简单
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
**输入：**root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
**输入：**root = []
输出：[]
示例 4：
**输入：**root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100] 内
-100 <= Node.val <= 100
**进阶：**递归算法很简单，你可以通过迭代算法完成吗？
2，相关知识点
二叉树的前序、中序、后序、层序遍历
3，解法
3.1，递归方法
使用了系统栈简化了计算
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public void recursion_pre(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
recursion_pre(root.left, res);
recursion_pre(root.right, res);
}
public void recursion_mid(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
recursion_mid(root.left, res);
res.add(root.val);
recursion_mid(root.right, res);
}
public void recursion_later(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
recursion_later(root.left, res);
recursion_later(root.right, res);
res.add(root.val);
}
public void recursion_level(TreeNode root, List<TreeNode> temp, List<Integer> res) {
if (temp.isEmpty()) {
return;
}
List<TreeNode> tempCur = new ArrayList<>();
for (TreeNode treeNode : temp) {
if (treeNode != null) {
res.add(treeNode.val);
tempCur.add(treeNode.left);
tempCur.add(treeNode.right);
}
}
recursion_level(root, tempCur, res);
}
|
3.2，迭代方法
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
public List<Integer> preOrderIteration_pre(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
if (pop.right != null) stack.push(pop.right);
if (pop.left != null) stack.push(pop.left);
res.add(pop.val);
}
return res;
}
public List<Integer> preOrderIteration_mid(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
TreeNode pop = stack.pop();
res.add(pop.val);
node = pop.right;
}
return res;
}
public List<Integer> preOrderIteration_later(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack1 = new ArrayDeque<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode pop = stack1.pop();
res.add(pop.val);
if (pop.left != null) stack1.push(pop.left);
if (pop.right != null) stack1.push(pop.right);
}
Collections.reverse(res);
return res;
}
|
3.3，Morris解法
感觉不是做竞赛的，可以只用知道有这样的一种方法即可
时间复杂度O（n）、空间复杂度O（1）