最近重新刷了树相关的题目，然后发现一个很有意思的点。
###1、题目列表如下：
- 层序遍历二叉树
- 层序遍历二叉树，按层输出
- 层序遍历n叉数
- 层序遍历n叉数，按层输出
- 获取二叉树/n叉数最左/最右下角的值
- 求二叉树或者n叉数的深度
2、分析
乍一看这些题目似乎都没啥联系，但只要分析一下，就不难发现，其实都是一个套路。
我们来分析遍历n叉数，按层输出这道题。
我们遍历每一层，然后标记当前到了哪一层，如果遍历到下一层的话，对应level进行累加即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result;
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}
|
3、再来回顾其他题目
我们来看其他题目，无非就是返回值少做更改而已。
比如返回二叉树/n叉数最左下角的值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result.get(result.size()-1).get(0); // 返回值稍微有些不同
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}
|
比如计算树的深度：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result.size(); // 返回result的大小即可
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}
|
骚操作不断，但是挺好玩的。我觉得学习、刷题，就是一个扩展思维、大胆猜想的过程。多多总结、多多进步！