算法-二叉树递归
1.前序遍历
public void preorder(TreeNode node){
if(node == null){
return;
}
System.out.print(node.val);
preorder(node.left);
preorder(node.right);
}
2.是否包含键值key
public boolean contain(TreeNode node,Key key){
if(node == null)
return false;
if(key == node.key)
return true;
if(contain(node.left,key)||contain(node.right,key))
return true;
return false;
}
3.释放二叉树
public void destroy(TreeNode node){
if(node == null)
return;
destroy(node.left);
destroy(node.right);
delete node;//不知道java咋delete的
count--;
}
LeeCode 104. Maximum Depth of Binary Tree
/**
* 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) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
LeeCode 111.Minimum Depth of Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null)
return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left+right+1 : Math.min(right,left)+1;
}
}
LeeCode 216.Invert Binary Tree
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
LeeCode 100.Same Tree
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}else if(p != null && q !=null){
if(p.val != q.val){
return false;
}else{
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}else{
return false;
}
}
}
LeeCode 101.Symmetric Tree
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
TreeNode left = root.left;
TreeNode right = reverse(root.right);
return isSame(left,right);
}
public TreeNode reverse(TreeNode root){
if(root == null){
return null;
}
TreeNode left = reverse(root.left);
TreeNode right = reverse(root.right);
root.left =right;
root.right = left;
return root;
}
public boolean isSame(TreeNode p,TreeNode q){
if(p == null && q == null){
return true;
}else if(p != null && q !=null){
if(p.val == q.val){
return isSame(p.left,q.left) && isSame(q.right,p.right);
}else{
return false;
}
}else{
return false;
}
}
}
TCP／IP
参考：https://toutiao.io/posts/3rdptu
一、TCP/IP模型
四层模型，链路层、网络层、传输层、应用层、层层封装
二、数据链路层
物理转换为0、1，MAC做唯一标识
三、网络层
IP协议
IP不是可靠协议，网络范围，协议中TTL规定该数据包在穿过多少个路由之后才会被抛弃（每穿过一个路由器，该数据包的TTL数值就会减少1，当该数据包的TTL成为零，它就会被自动抛弃。）
ARP及RARP协议
ARP 根据IP获取MAC地址、主机有自己的ARP高速缓存、查询键值对不存在，广播，符合条件主机回复，主机更新
ICMP协议
保证数据送达，原理（用类型码为0的ICMP发请 求，受到请求的主机则用类型码为8的ICMP回应）
四、Traceroute
侦测主机到目的主机之间所经路由情况，原理（它收到到目的主机的IP后，首先给目的主机发送一个TTL=1的UDP数据包，而经过的第一个路由器收到这个数据包以后，就自动把TTL减1，而TTL变为0以后，路由器就把这个包给抛弃了，并同时产生 一个主机不可达的ICMP数据报给主机。主机收到这个数据报以后再发一个TTL=2的UDP数据报给目的主机，然后刺激第二个路由器给主机发ICMP数据 报。如此往复直到到达目的主机。这样，traceroute就拿到了所有的路由器IP。）
五、TCP/UDP
UDP
面向报文（发送给IP层报文，不切分，必须选择合适大小的报文），适用通讯质量有要求的场景。
TCP
面向字节流（把报文当做一连串无结构的字节流，切分），适用网络通讯质量不高，要求通讯速度尽量快的场景。
六、DNS
域名和IP相互映射的分布式数据库、UDF，53端口
七、TCP连接的建立与终止
疑问
1.java的delete node如何操作
2.LeeCode 111.Minimum Depth of Binary Tre有疑问
3.第四层是数据链路层，这个层次为待传送的数据加入一个以太网协议头，并进行CRC编码，为最后的数据传输做准备。
4.数据链路层特点：
封装成帧: 把网络层数据报加头和尾，封装成帧,帧头中包括源MAC地址和目的MAC地址。
透明传输:零比特填充、转义字符。
可靠传输: 在出错率很低的链路上很少用，但是无线链路WLAN会保证可靠传输。
差错检测(CRC):接收者检测错误,如果发现差错，丢弃该帧。
5.ping结果细节
网友评论