su29029的博客

因为心在那里

0%

20210307学习记录

Posted on Edited on In Views: Valine:
Symbols count in article: 26k字 Reading time ≈ 24 mins.

2021-03-07 学习记录

今天的学习内容：

  1. 数据结构：树-二叉树（二叉树的非递归遍历，由前/中序或中/后序序列创建二叉树）
  2. Leetcode刷题：#94 二叉树的中序遍历；#105 从前序与中序遍历序列构造二叉树；#226 翻转二叉树
  3. 复习web渗透相关内容

1. 数据结构：二叉树

今天补充了一下二叉树的非递归遍历和另一种创建二叉树的方法。

首先是二叉树的非递归遍历。我们递归遍历二叉树的时候，操作系统维护了一个递归调用栈，非递归的话我们需要去模拟这个栈。

前序非递归遍历的实现

对于任意节点p，首先访问节点p并入栈，随后判断左孩子是否为空，为空则取栈顶节点并出栈，并将当前栈顶节点的右孩子作为当前节点p；若不为空则将p的左孩子作为节点p。一直遍历到p为nil且栈为空则遍历结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (binaryTree *BinaryTree) IterTraversePreOrder() interface{} {
	var res []interface{}
	var stack []*BinaryTree

	root := binaryTree
	for root != nil || len(stack) > 0 {
		for root != nil {
			res = append(res, root.val)
			stack = append(stack, root)
			root = root.left
		}
		if len(stack) != 0 {
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			root = root.right
		}
	}
	return res
}
中序非递归遍历的实现

中序和前序相似，按照左-根-右的方式遍历，那么还是先一直将p节点的左孩子入栈，直到左孩子为空，取栈顶元素并出栈，访问保存该栈顶节点，随后将p置为该栈顶节点的右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func (binaryTree *BinaryTree) IterTraverseInOrder() interface{} {
	var res []interface{}
	var stack []*BinaryTree

	root := binaryTree
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.left
		}
		if len(stack) != 0 {
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res = append(res, root.val)
			root = root.right
		}
	}
	return res
}

后序遍历的非递归实现

后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这对流程控制造成了一定的影响。这里的一个解决方案是通过记录访问当前节点之前访问的节点，判断这两个节点的关系以确定当前节点之前访问的那个节点的左右孩子是否已被访问过。

对于任一结点P，先将其入栈。如果P是叶子节点，则直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈。（注意顺序，先右后左，这样才能保证遍历的时候是左-右-根的顺序）。

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
func (binaryTree *BinaryTree) IterTraversePostOrder() interface{} {
	var res []interface{}
	var stack []*BinaryTree

	var cur *BinaryTree
	var pre *BinaryTree = nil

	root := binaryTree
	stack = append(stack, root)
	for len(stack) != 0 {
		cur = stack[len(stack)-1]

		if (cur.left == nil && cur.right == nil) || (pre != nil && (pre == cur.left || pre == cur.right)) {
			res = append(res, cur.val)
			stack = stack[:len(stack)-1]
			pre = cur
		} else {
			if cur.right != nil {
				stack = append(stack, cur.right)
			}
			if cur.left != nil {
				stack = append(stack, cur.left)
			}
		}
	}
	return res
}
由前/中序或中/后序序列创建二叉树

我们知道知道前序和中序或者中序和后序的二叉树遍历序列，我们可以重建出这个二叉树。主要的思想是找到前序或后序序列中根节点在中序中的位置，前序序列的第一个节点是根节点，后序序列的最后一个节点是根节点，中序中根节点的左侧是根节点的左侧节点，右侧则是右侧节点，通过这个来不断切分缩小到一个个子树。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
func CreateByTwoSequences(seq1 interface{}, seq2 interface{}, flag int) *BinaryTree {
	slice1, ok1 := CreateAnyTypeSlice(seq1)
	slice2, ok2 := CreateAnyTypeSlice(seq2)
	if !ok1 || !ok2 {
		fmt.Errorf("not slices")
		return nil
	}

	if len(slice1) != len(slice2) {
		fmt.Errorf("invalid parameters")
		return nil
	}

	var createByPreAndIn func(seq1 []interface{}, seq2 []interface{}) *BinaryTree
	var createByInAndPost func(seq1 []interface{}, seq2 []interface{}) *BinaryTree

	var binaryTree = new(BinaryTree)
	var inPos map[interface{}]int
	inPos = make(map[interface{}]int)

	createByPreAndIn = func(seq1 []interface{}, seq2 []interface{}) *BinaryTree {
		if len(seq1) == 0 {
			return nil
		}

		root := &BinaryTree{seq1[0], nil, nil}

		i := 0
		for ; i < len(seq2); i++ {
			if seq2[i] == seq1[0] {
				break
			}
		}

		root.left = createByPreAndIn(seq1[1:i+1], seq2[:i])
		root.right = createByPreAndIn(seq1[i+1:], seq2[i+1:])

		return root
	}

	createByInAndPost = func(seq1 []interface{}, seq2 []interface{}) *BinaryTree {
		if len(seq2) == 0 {
			return nil
		}

		root := &BinaryTree{seq2[len(seq2)-1], nil, nil}

		i := 0
		for ; i < len(seq1); i++ {
			if seq1[i] == seq2[len(seq2)-1] {
				break
			}
		}

		root.left = createByInAndPost(seq1[:i], seq2[:i])
		root.right = createByInAndPost(seq1[i+1:], seq2[i:len(seq1)-1])
		return root
	}

	// save the inOrder's node, instead of traversing the inOrder sequence in the recursion
	for i := 0; i < len(slice1); i++ {
		inPos[slice1[i]] = i
	}

	if flag == 1 {
		binaryTree = createByPreAndIn(slice1, slice2)
	}
	if flag == 2 {
		binaryTree = createByInAndPost(slice1, slice2)
	}

	return binaryTree
}

2. Leetcode刷题

今天刷的这三个题基本和复习的数据结构内容重合，只有第三题反转二叉树有些不同，这里记录一下。

#226 翻转二叉树

这个题顾名思义，就是将所有节点的子结点左右镜像对称，左孩子变成右孩子，右孩子变成左孩子。思路很明确，遍历这个二叉树，每遍历一个节点时将这个节点的左右孩子交换，然后继续遍历，直到节点为nil时返回。

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.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    root.Left, root.Right = root.Right, root.Left

    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

web渗透相关内容复习

最近除了复习数据结构还准备了护网的面试，（恰点钱hhhhh）今天晚上也复习了一点web渗透相关的内容，这里记录一下。

(1)mysql注入写shell的函数和条件

函数 into dump_file “path/to/file” 或 into outfile “path/to/file”

条件 secure_file_priv 置为true

(2)mysql数据库5.0以下和5.1以上版本注入有什么区别

5.0以下版本mysql没有information_schema数据库，这个数据库里面存放着所有数据库的信息（数据库名，表名，列名，列属性，对应权限等），5.0以下没有information_schema数据库时，需要通过盲注的方式获取表名列名。

(3)常见报错注入函数

extractvalue(), updatexml(), multipoint(), linestring(), exp(), polygen(),multipolygen(),multilinestring()等

(4)如何获取网站根路径

可以通过让代码报错的方式获取网站根路径，或者是故意请求一个不存在的页面使服务器报错，从报错信息中也许可以获取。

(5)木马免杀
  1. shellcode多次编码。exe文件通过msf x86/shikata_ga_nai编码12次以上可以免杀
  2. upx加壳
(6)xss防御

xss：攻击者通过各种办法，在用户访问的网页中插入自己的脚本，让其在用户访问网页时在其浏览器中进行执行。攻击者通过插入的脚本的执行，来获得用户的信息，比如cookie，发送到攻击者自己的网站

xss成因：对URL中的参数，对用户输入提交给web server的内容，没有进行充分的过滤

防御方法：对提交的所有内容进行过滤，对url中的参数进行过滤，过滤掉会导致脚本执行的相关内容；然后对动态输出到页面的内容进行html编码，使脚本无法在浏览器中执行。

(7)csrf防御

csrf：攻击者诱导受害者进入第三方网站，在第三方网站中，向被攻击网站发送跨站请求。利用受害者在被攻击网站已经获取的注册凭证，绕过后台的用户验证，达到冒充用户对被攻击的网站执行某项 操作的目的。

csrf防御方法：①阻止不明外域访问：同源检测、SameSite Cookie；②提交时附加本域才能获取的信息，例如csrf token

(8)shiro反序列化漏洞

shiro-550 rememberMe反序列化漏洞：

Shiro提供了记住密码的功能，用户登录成功后会生成经过加密并编码的cookie，在服务端rememberMe的cookie值先进行base64解码然后AES解密再反序列化，就导致了反序列化rce漏洞。

命令=>序列化=>AES加密=>base64编码=>RememberMe Cookie值

影响版本：Apache Shiro < 1.2.4 特征：返回包中包含rememberMe=deleteMe字段

shiro-721 Shiro Padding Oracle Attack

由于Apache Shiro cookie中通过 AES-128-CBC 模式加密的rememberMe字段存在问题，用户可通过Padding Oracle 加密生成的攻击代码来构造恶意的rememberMe字段，并重新请求网站，进行反序列化攻击，最终导致任意代码执行。
影响版本：Apache Shiro < 1.4.2版本。

(9)redis未授权访问

产生原因：redis默认情况绑定0.0.0.0:6379，暴露在公网，如果没有任何防火墙策略，且redis无密码认证的话，会导致任意用户在可以访问目标服务器的情况下未授权访问 Redis 以及读取 Redis 的数据。

危害：敏感信息泄露，写入后门文件，最严重的如果redis以root身份运行，黑客可以直接写入ssh公钥，通过ssh远程登录服务器。

(10)安全工具的使用 burpsuite sqlmap 蚁剑
(11)linux运维基础 查看账号文件 cpu占用率 内存占用率 进程相关操作 日志（ssh登录日志 中间件日志）历史命令 历史登录用户 当前在线用户等
(12)linux加固

修改密码长度，复杂度；禁用删除无用账号；检查特殊账户；设置会话超时；禁止root ssh登录，修改ssh默认端口；隐藏系统版本；关闭不必要的服务。

(13)ms12_020 rdp远程代码执行漏洞原理：use-after-free 利用方式，使用msf进行操作