思想
利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了，所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点，对于前序遍历、我们可以先将当前的值放进结果集中，表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程，也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。
实现
|
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
res.add(root.val);
stack.add(root);
root = root.left;
}
TreeNode cur = stack.pop();
root = cur.right;
}
return res;
}
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
res.add(root.val);
stack.add(root);
root = root.left;
} else {
TreeNode cur = stack.pop();
root = cur.right;
}
}
return res;
}
public List<Integer> preorderTraversal3(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
return res;
}
public List<Integer> preorderTraversal4(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
res.add(root.val);
if (root.right != null) {
queue.addFirst(root.right);
}
if (root.left != null) {
root = root.left;
while (root != null) {
res.add(root.val);
if (root.right != null) {
queue.addFirst(root.right);
}
root = root.left;
}
}
}
return res;
}
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.add(root);
root = root.left;
} else {
TreeNode cur = stack.pop();
res.add(cur.val);
root = cur.right;
}
}
return res;
}
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.add(root);
root = root.left;
}
TreeNode cur = stack.pop();
res.add(cur.val);
root = cur.right;
}
return res;
}
public List<Integer> postorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
Collections.reverse(res);
return res;
}
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty()) {
while (root != null) {
res.add(root.val);
stack.push(root);
root = root.right;
}
TreeNode cur = stack.pop();
root = cur.left;
}
Collections.reverse(res);
return res;
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null)return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size!=0){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!= null){
queue.offer(cur.right);
}
size --;
}
ret.add(list);
}
return ret;
}
|
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/qq_45859087/article/details/119141358