总结一下二叉树常见的遍历方式
二叉树节点类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
|
由于二叉树的天然递归性，一般二叉树的题目都是用递归的方法写，代码会简洁易读，但是想要写出漂亮的递归，需要进行大量的练习，递归易读难写。
二叉树的遍历当然也可以用迭代实现，不过代码会比递归繁琐一些，因为需要手动维护一个栈，而递归栈是由系统帮我们维护的。迭代也有优点，那就是当递归层次过深时，会爆栈，而迭代基本不会。
想要理解各种遍历代码的意思，建议现在纸上手动遍历二叉树，将其中的过程理解清楚，才能更好地理清代码逻辑，不然越看越糊涂。
前序遍历
题目练习：二叉树的前序遍历
前序遍历的顺序是“根节点 - 左子树 - 右子树”，即先访问根节点，再依次访问左子树、右子树。在访问子树时，也要遵循“根 - 左 - 右”的顺序。
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
preorder(root);
return list;
}
public void preorder(TreeNode node) {
if (node == null) {
return;
}
list.add(node.val);
preorder(node.left);
preorder(node.right);
}
}
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
ans.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return ans;
}
}
|
中序遍历
题目练习：二叉树的中序遍历
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return ans;
}
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
ans.add(node.val);
inorder(node.right);
}
}
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
ans.add(node.val);
node = node.right;
}
return ans;
}
}
|
后序遍历
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
postorder(root);
return ans;
}
public void postorder(TreeNode node) {
if (node == null) {
return;
}
postorder(node.left);
postorder(node.right);
ans.add(node.val);
}
}
|
迭代
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
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root, prev = null;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
if (node.right == null || node.right == prev) {
ans.add(node.val);
prev = node;
node = null;
} else {
stack.push(node);
node = node.right;
}
}
return ans;
}
}
|
层序遍历
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
|
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
temp.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ans.add(temp);
}
return ans;
}
|
