Problem 102 107

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5

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

Solution

key：

• 层序遍历
• 递归

在Java中可以先定义一个List保存结果,List里面再嵌入ArrayList来记录每一层的数据

List<List> res = new ArrayList<>();

res.add(new ArrayList<>());

将递归中的root节点追加进入res.get(level)的数组中

res.get(level).add(root.val);

通过递归完成算法

travelsal(root.left,level+1);
travelsal(root.right,level+1);

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        travelsal(root, 0);
        return  res;
    }

    private void travelsal(TreeNode root,int level) {
        if(root==null){
            return;
        }
        if(level==res.size()){
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        travelsal(root.left,level+1);
        travelsal(root.right,level+1);
    }
}

接下来是107，是102的变种，改成了叶节点开始遍历

difficulty：Easy

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
6

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

key

题目本身没有设置太多的难度，我们只需要将level实现数组的内层数组的倒序就可以了

res.get(level).add(root.val);
change this code to
res.get(res.size()-i-1).add(root.val);

原本判断新增数组的语句变成在第0个位置新增一个数组

if(i >= res.size()){
res.add(0,new ArrayList());
}

迫于比较好奇，下载了egg-redis，看看他如何将node直接可以引用的包，封装成为egg的插件

核心代码通过

Prolem 104

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

key

判断树的深浅，采用

int left = max(root.left);
int right = max(root.right);
return Math.max(left,right) + 1;

//或者简写

return Math.max(max(root.left) + 1, max(root.right) + 1);

进行递归

Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Depth of Binary Tree.

Memory Usage: 39.2 MB, less than 94.62% of Java online submissions for Maximum Depth of Binary Tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
         return max(root);
    }
    public int max(TreeNode root){
        if (root == null) {
            return 0;
        }
        return Math.max(max(root.left) + 1, max(root.right) + 1);
    }
}

Problem101

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5

  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

key

一道验证树是否是对称的问题，主要采取递归的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
    public boolean isMirror(TreeNode root,TreeNode self){
        if(root==null && self==null)return true;
        if(root==null ||self==null) return false;
        return root.val==self.val && isMirror(root.left,self.right)&&isMirror(root.right,self.left);
        
    }
}

AMD:Asynchronous Module Definition (RequireJS)

CMD:Common Module Definition（SeaJS）

AMD

待补充，import-export

CMD

define Function

一个文件就是一个模块，在我们的代码外层，会套上一层CMD规范,这也就是为什么我们可以直接引用require,export,module的原因

1
2
3

define(function(require, exports, module) {
  // code
});

单个参数

1
2
3
4

define(factory)
param-->factory:funtion|Object|String
define({ "foo": "bar" });
define('I am a template. My name is {{name}}.');

多个参数define define(id?, deps?, factory)

1
2
3
4
5

define('hello', ['jquery'], function(require, exports, module) {
  // code
});
id：String模块标识
deps：Array模块依赖

define.cmd Object

1
2
3
4

if (typeof define === "function" && define.cmd) {
  // 有 Sea.js 等 CMD 模块加载器存在
}
//用来判断当前页面是否有CMD模块加载器

require Function

同步加载

1
2
3
4
5
6
7
8
9

define(function(require, exports) {

  // 获取模块 a 的接口
  var a = require('./a');

  // 调用模块 a 的方法
  a.doSomething();

});

require.async Function

异步加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14

define(function(require, exports, module) {

  // 异步加载一个模块，在加载完成时，执行回调
  require.async('./b', function(b) {
    b.doSomething();
  });

  // 异步加载多个模块，在加载完成时，执行回调
  require.async(['./c', './d'], function(c, d) {
    c.doSomething();
    d.doSomething();
  });

});

require.resolve

返回解析后的绝对路径

exprots

return Object，对外提供接口

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

define(function(require, exports) {

  // 对外提供 foo 属性
  exports.foo = 'bar';

  // 对外提供 doSomething 方法
  exports.doSomething = function() {};

});

retrun可以实现同等效果
define(function(require) {

  // 通过 return 直接提供接口
  return {
    foo: 'bar',
    doSomething: function() {}
  };

});
以及个人不太喜欢的缩略写法
define({
  foo: 'bar',
  doSomething: function() {}
});

但以下写法是错误的

1
2
3
4
5
6
7
8
9

define(function(require, exports) {

  // 错误用法！！!
  exports = {
    foo: 'bar',
    doSomething: function() {}
  };

});

exports 仅仅是 module.exports 的一个引用。在 factory 内部给 exports 重新赋值时，并不会改变 module.exports 的值。因此给 exports 赋值是无效的，不能用来更改模块接口。

我说句简单的话：exports和module.exports，都是地址，指向同一个内容，如果你给exports赋值了一个新对象，他指向的内容就完全变了，和module.exprots就指向不是同一个地方了

module

modeule是一个对象，存储与当前模块相关联的一些属性和方法，默认为{}

module:function

module.id:String模块标识

module.url：String返回绝对路径（默认id=url，除非手写id）

module.dependencies:Array模块依赖

module.export:Object 大部分情况下和exports通用，但如果模块是一个类，就应该直接赋值给module.exports，这样调用就是一个类的构造器，可以直接new实例

1
2
3
4
5
6
7
8

module.exports=new Person();
const p = require(./xxx.js);
p.say();
//or
exports.p = new Person();
const {p} = require(./xxxjs);
p.say();

Problem105

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

key

题目是一个根据前序中序，生成二叉树的题目

前序遍历有个特点：根节点在前面，root -left-right

则遍历到3作为root，根据中序可以知道左子树是9，右子树是15 20 7

然后遍历9作为root，根据中序得到没有左子树，没有右子树

然后遍历20作为root，依次类推可以得到

1
2
3

TreeNode root = new TreeNode(rootVal);
root.left = buildTree(pre, preStart+1, preStart+len, in, inStart, rootIndex-1);
root.right = buildTree(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd);

其中insort比较好理解，确定root后

左子树在inStart, rootIndex-1之间

右子树在rootIndex+1, inEnd之间

对于presort

int len = rootIndex - inStart;获得root的左子树长度（根据中序获取rootIndex）

左子树在preStart+1, preStart+len之间

右子树在preStart+len+1, preEnd之间

Solution

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
        if(inStart > inEnd || preStart > preEnd)
            return null;

        int rootVal = pre[preStart];
        int rootIndex = 0;
        for(int i = inStart; i <= inEnd; i++){
            if(in[i] == rootVal){
                rootIndex = i;
                break;
            }
        }

        int len = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(pre, preStart+1, preStart+len, in, inStart, rootIndex-1);
        root.right = buildTree(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd);

        return root;
    }
}

tip

参考于百度，在递归条件乱了

Problem94

Given a binary tree, return the inorder traversal of its nodes’ values.

给定一二叉树，中序遍历输出

ps:preorder,inorder,postorder，前中后

Key

recursive approach

利用递归解决B树的遍历问题，这种问题的代码其实大同小异，前中后的遍历输出，只需要调整递归部分即可

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

//preorder
public void preorder(node t)
	if (t != null) {
		System.out.print(t.value + " ");
		preorder(t.left);
		preorder(t.right);
	}
}
//inorder
public void inorder(node t)
{
	if (t != null) {
		inorder(t.left);
		System.out.print(t.value + " ");
		inorder(t.right);
	}
}
//postorder
public void postorder(node t)
{
    if (t != null) {
        postorder(t.left);
        postorder(t.right);
        System.out.print(t.value + " ");
    }
}
//leverorder

Solution

Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.

Memory Usage: 37.9 MB, less than 5.11% of Java online submissions for Binary Tree Inorder Traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        inorder(root, res);
        return res;
    }
     public void inorder(TreeNode root, List < Integer > res) {
        if (root != null) {
            inorder(root.left, res);
            res.add(root.val);
            inorder(root.right, res);
        }
    }
}

Complexity Analysis

• Time complexity : O(n)O(n). The time complexity is O(n)O(n) because the recursive function is T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1.
• Space complexity : The worst case space required is O(n)O(n), and in the average case it’s O(\log n)O(logn) where nn is number of nodes.

stack

solution还提供了另外一种方法通过stack pop的方式来完成：

https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

Morris

同上

I find hexo’s theme:nexT v7.7.2 has some new features

native dark mode

we can set

1

darkmode:true

to open native dark mode

and there are other features like

• support MathJax v3.0,we use $$
• add next_config helper

how to update newest version

1.git clone https://github.com/theme-next/hexo-theme-next themes/next

or in releases to download newest source code

2.copy file to hexo/theme/ such as :

/themes/hexo-theme-next-7.7.2/

3.open hexo’s _config.yml,and change theme’s value to hexo-theme-next-7.7.2 and u change your them successfully

4.update /themes/hexo-theme-next-7.7.2/_config.yml

Last , u can create new post to log your daily life

1

yarn upgrade caniuse-lite browserslist

and these days ,zehai.info ,may Expired ,sad

今天确实发生了一些事情，避之不谈

让我想起来了之前我在bili遇到的一件事情，一个up主癌症，自己经济能力不是很好，拍了一些很粗糙，没有剪辑过的视频，大意交代了自己得病，没有钱，拍了病历本，化验单，希望大家有能力的捐一点，后来up大概是拿到了一部分钱，具体多少我不太清楚，后来不知道发生了什么，画风开始转变

up视频的下面出现了很多评论

评论up有两个手机，家里有钱，然后up就对焦给大家看了他的两个手机，我记得两个都是红米类似的便宜机器，而且买了很久了

后来又人评论他家多有钱，然后up就拍下了回家和奶奶在一起的场面（当时已经没钱住院，就回家筹钱换医院试试）

后来又有人评论up主根本就没病，出来骗人钱，up就拍视频给人看治疗过程中的病历，化验单，至少我看不出来造假的证据

后来up出院了，买了张车票回家，和一个月前相比头发掉了很多，弹幕里面各种质疑，评论里面一片质疑，

亲身经历，环顾整个过程，我没有给up捐赠一分钱，也没有给予他任何帮助，就看了他整个生病的过程，从开始的加油，变成了一个‘骗子’，人们存在于网络之后，确实可以发表自己对于一件事情的看法，我想我如果是那个up，深陷其中一定很无奈

陈述结束

最后疫情一定会过去的

今天中午有收到Egg团队公开的文件调查，提及了很多技术名词，虽然不一定用到，但我也觉得列举出来会方便大家了解和比较，后续可能更新我用过的部分

代码检查工具

• ESLint
• JSCS
• JSHint
• JSDoc
• Standard
• TSLint
• Flow

使用感受

解决了以下问题

• node是一门弱语言，进行校验（非变量类型校验，仅校验变量是否声明，是否可改等）
• node在use strict模式下，eslint可以校验
• 团队合作，防止队友挖坑

其实ESLint只是一种语法校验，更多的还有流程上的规范，就像网传阿里的开发规范一样，就好比node中你可以用类的语法糖，也可以用原型，当一件事情有多种实现方式时，需要规范来选择一个普遍公用的，易维护，易扩展的方案

除去语法校验，还有TS的类型校验，比如GIT的分支规范，如master,staging,backup,develop,other branch

转义语言

• TS
• ClojureScript
• CoffeeScript
• Dart
• Elm
• Scala.js
• Haxe
• Nim
• PureScript
• Reason

转移语言是2019年聊的比较多的，解决问题：

• 类型校验，能够很好解决JS开发中，你不知道这个object里面有什么key，或者某个对象里面有什么方法（egg.js实际开发过程中，ctx.service.v1.handlexxx()就ctrl跳转不了，也不会有提示）

WEB框架

• Express
• Koa
• Egg
• Nest.js
• Next.js
• Fastify.js
• Hapi.js
• Restify.js
• Loopback.io
• Sails.js
• Midway.js

面试常被问到框架的问题，因为很多公司不会将项目搭建在原生的node服务上

• 缺少约束，合作模式下，个人有个人的风格
• 项目配置繁琐，很多东西配置零散堆放
• 重复造轮子，框架提供较好的轮子
• 安全事宜，框架处理
• etc

一个好的框架事半功倍，
express是一个非常轻量的框架

• fast
• unopinionated(干净的)
• minimalist

Egg是一个企业级框架，约定大于配置

• Provide capability to customizd framework base on Egg（可扩展）
• Highly extensible plugin mechanism（插件牛逼）
• Built-in cluster（多进程牛逼）
• Based on Koa with high performance（企业级别性能优异）
• Stable core framework with high test coverage（稳定）
• Progressive development（业务迭代，代码可以渐进继承）

数据库

• MySQL
• PostgreSql
• Redis
• MongoDB
• SQL Server
• SQLLite
• influxdb
• HBASE
• TiDB
• Oracle
• DB2

数据库是仅此于语言本身，另外的考点了，因为没有一个服务不涉猎存储，而数据库作为系统的数据基础，不仅重要也成为了面试的重点

• mysql等关系型数据库，范式，事务，innodb，读写分离，分表
• Mongo,Redis等非关系型数据基础类型，聚合等

反向代理

• Nginx

• Tomcat

• Apache

• 解决负载均衡

• 预处理一些请求，如过滤重复请求

进程管理

• Docker
• PM2
• forever
• naught
• node-supervisor
• Supervisord(Unix)

docker集大成者，在微服务等场景应用较多

RPC方式

• HTTP
• Thrift
• gRPC
• dubbo
• MQ

开发场景

• 服务端API
• SSR应用
• Proxy层
• BFF层
• 代码片段，如Spark代码片段
• CLI & 工具

tips