ARTS-第11周

发表于

ARTS （第11周）

这个礼拜事情真多。
发觉劳逸结合很重要，而最好的休息方式就是放空大脑，什么都不要去想。

本周：

二叉树的按层次遍历

（ps：后来了解到这就是广度优先搜索算法）

Algorithm 算法

二叉树的层次遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路是就是创建一个辅助队列 （我这里用LinkedList）保存每一层节点的数据（第一次循环处理第一层第二次第二层，以此类推），当每个数据处理完了，就丢进当前数据里的子节点数据。

因为每次处理之前size的值从一开始固定了 所以再往队列里丢入子节点不会做多余的处理。

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
public static List<List<Integer>> levelOrder(TreeNode root) {
	//想吐槽一句 有的题目会给null的案例 有的题目又没有null的案例
	if(root == null)
        return new ArrayList<>();
	List<List<Integer>> r = new ArrayList<List<Integer>>();
	//提交leetcode 使用这个LinkedBlockingQueue类 的时候报错 
	//LinkedBlockingQueue<TreeNode> help = new LinkedBlockingQueue<TreeNode>();
	LinkedList<TreeNode> help = new LinkedList<TreeNode>();
	help.add(root);
	while(help.size()>0){
		int size = help.size();//因为这个SIZE一开始固定了 所以再丢入子节点不会做多余的处理
		List<Integer> level = new ArrayList<Integer>();
		for (int i = 0; i < size; i++) {
			TreeNode o = help.poll();
			//TreeNode o = help.remove(0);
			level.add(o.val);
			if(o.left!=null){
				help.add(o.left);
			}
			if(o.right!=null){
				help.add(o.right);
			}
		}
		r.add(level);
	}
	return r;
}

Review 英文文章

https://hadoop.apache.org/docs/r3.2.0/

Apache Hadoop 3.2.0的更新以及介绍。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的27篇

学习了用树来求解递归的时间复杂度

Share 分享

Google 都在用的 6 个休息小技巧，让你工作效率翻倍

https://blog.csdn.net/ityouknow/article/details/90684761