forked from algorithm024/algorithm024
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPostorder_590.java
More file actions
113 lines (104 loc) · 3.28 KB
/
Copy pathPostorder_590.java
File metadata and controls
113 lines (104 loc) · 3.28 KB
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.util.*;
public class Postorder_590 {
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
/**
* 首先用递归算法来求解
* @param root
* @return
*/
// 1. List集合是有序的么？--是
// 2. foreach遍历null和空集分别是什么情况？--遍历null抛空指针，遍历空集无异常
// 3. 如何防止输入[]的情况不输出null？--递归终止条件返回空集
public List<Integer> postorder1(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 遍历各孩子节点
// 这里没有空指针异常说明children是一个空集
for (Node node : root.children) {
result.addAll(postorder1(node));
}
// 添加根节点的值
result.add(root.val);
return result;
}
/**
* 迭代算法，借助辅助栈来实现
* @param root
* @return
*/
// 1. 为什么这种算法会超出内存限制
public List<Integer> postorder2(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.add(root);
while(!stack.isEmpty()) {
// 取栈顶元素
Node node = stack.peek();
if (node.children.isEmpty()) {
// 如果栈顶元素的孩子节点为空集，则输出栈顶元素的值并出栈
result.add(stack.pop().val);
} else {
// 否则将栈顶元素的孩子节点依次推入堆栈
for (Node childNode : node.children) {
stack.push(childNode);
}
}
}
return result;
}
/**
* LeetCode官方解法使用栈优化
* @param root
* @return
*/
// 1. 用迭代法咋比用递归算法耗时还要长
public List<Integer> postorder3(Node root) {
LinkedList<Integer> result = new LinkedList<>();
if (root == null) {
return result;
}
Deque<Node> stack = new ArrayDeque<>();
stack.addLast(root);
while (!stack.isEmpty()) {
// 将栈顶元素出栈
Node node = stack.pop();
// 使用LinkedList逆序插入
result.addFirst(node.val);
// 否则将栈顶元素的孩子节点依次推入堆栈
for (Node childNode : node.children) {
// 子节点null值不入栈
if (childNode != null) {
stack.push(childNode);
}
}
}
return result;
}
// 1. 关于foreach空集的测试
public static void main(String[] args) {
List<Integer> list = null;
for (int a : list) {
System.out.println("测试foreach一个null值");
}
list = Collections.emptyList();
for (int a : list) {
System.out.println("测试foreach一个空集");
}
}
}