【数据结构和算法】BFS和DFS两种方式解决

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

### BFS打印

```import java.util.ArrayList;

/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
import java.util.Queue;

public class Solution {

public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null)
return res;
boolean leftToRight = true;
while (!queue.isEmpty()) {
ArrayList<Integer> level = new ArrayList<>();
//统计这一行有多少个节点
int count = queue.size();
//遍历这一行的所有节点
for (int i = 0; i < count; i++) {
//poll移除队列头部元素（队列在头部移除，尾部添加）
TreeNode node = queue.poll();
//判断是从左往右打印还是从右往左打印。
if (leftToRight) {
} else {
}
//左右子节点如果不为空会被加入到队列中
if (node.left != null)
if (node.right != null)
}
leftToRight = !leftToRight;
}
return res;
}

}```

```import java.util.ArrayList;
import java.util.Deque;

public class Solution {

public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null)
return res;
//双端队列，两边都可以操作
//添加到队列的头
while (!deque.isEmpty()) {
ArrayList<Integer> level = new ArrayList<>();
//统计这一行有多少个节点
int count = deque.size();
//遍历这一行的所有节点
TreeNode cur;
for (int i = 0; i < count; i++) {
if (res.size() % 2 == 1) {
//从左边往右边打印
//移除队列头部的元素，如果子节点不为空加入到队列的尾部
cur = deque.removeFirst();
if (cur.right != null)
if (cur.left != null)
} else {
//从右边往左边打印
//移除队列尾部的元素，如果子节点不为空加入到队列的头部
cur = deque.removeLast();
if (cur.left != null)
if (cur.right != null)
}
}
}
return res;
}

}```

### DFS打印

```import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
travel(root, res, 0);
return res;
}

private void travel(TreeNode cur, ArrayList<ArrayList<Integer>> res, int level) {
if (cur == null)
return;
//如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
if (res.size() <= level) {
ArrayList<Integer> newLevel = new ArrayList<>();
}
//遍历到第几层我们就操作第几层的数据
List<Integer> list = res.get(level);
//这里默认根节点是第0层，偶数层相当于从左往右遍历，
// 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
// 要把数据添加到集合的开头
if (level % 2 == 0)
else
//分别遍历左右两个子节点，到下一层了，所以层数要加1
travel(cur.left, res, level + 1);
travel(cur.right, res, level + 1);
}

}```

#### 如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解

2022-12-29 13:09
Durham University_2022

2022-12-05 02:35

2022-12-28 10:16

2022-12-10 09:46

2022-12-29 18:54

2022-12-10 21:18

2022-12-08 16:11

2022-12-23 12:11

2022-12-15 02:17

2022-12-13 18:23

5 1 评论