#include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode * rebin(vector<int> pre, vector<int> in) { // 首先看看有米有东西吧 // 一个元素都没有的话 // 这个二叉树就只有一个NULL节点 // 直接返回即可w if (pre.size() == 0) return nullptr; // 根据前序遍历的定义 根节点一定在前序遍历结果的第一个位置上 // 而中序遍历的话 根结点必然需要等到它的左子树都输出完才会出现 // 利用这一点我们分开左右子树 int root_value = pre[0]; TreeNode * root = new TreeNode(root_value); // 找到根节点在中序遍历里的下标 // 以此分开左右子树 int root_index_of_in = 0; for (int i = 0; i < in.size(); i++) { if (in[i] == root_value) { root_index_of_in = i; break; } } // 分开左右子树 // 按原始的顺序分别保存左右子树的前序遍历和中序遍历 vector<int> left_pre, left_in, right_pre, right_in; // 先是左子树 for (int i = 0; i < root_index_of_in; i++) { // 这里需要+1 // 因为前序遍历的话 第一个元素是根节点 // 所以需要跳过当前(下标为0)的这个元素 left_pre.emplace_back(pre[i+1]); left_in.emplace_back(in[i]); } // 然后是右子树 for (int i = root_index_of_in + 1; i < in.size(); i++) { right_pre.emplace_back(pre[i]); right_in.emplace_back(in[i]); } // 既然左右子树的前序遍历和中序遍历都有了 // 和我们一开始拿到的初始条件很相似吧~ // 那么递归吧w root->left = rebin(left_pre, left_in); root->right = rebin(right_pre, right_in); return root; } // 三种遍历方式~/ typedef enum { PRE_ORDER, IN_ORDER, POST_ORDER, } TreeTraversal; void print_with_order(TreeNode * root, TreeTraversal order) { // 如果根节点是空的 // 那啥都不用说直接返回吧 if (root == nullptr) return; // 看看使用什么序来遍历 // 本质上仅仅只是输出当前root节点的位置不一样 if (order == PRE_ORDER) { cout << root->val << ' '; print_with_order(root->left, order); print_with_order(root->right, order); } else if (order == IN_ORDER) { print_with_order(root->left, order); cout << root->val << ' '; print_with_order(root->right, order); } else { print_with_order(root->left, order); print_with_order(root->right, order); cout << root->val << ' '; } } int main(int argc, const char * argv[]) { vector<int> pre = {1,2,4,7,3,5,6,8}; vector<int> in = {4,7,2,1,5,3,8,6}; TreeNode * head = rebin(pre, in); // 用构建好的树输出前序和中序遍历来验证~ cout << "pre: "; print_with_order(head, PRE_ORDER); cout << endl; cout << "in: "; print_with_order(head, IN_ORDER); cout << endl; }
Category Archives: C++
IEEE 802.11 Denial-of-Service: RSN IE Poisoning
前面提到的方法都需要发送大量的数据包,而这篇 post 中的方法仅需要嗅探再加上少量的包就可以实现对使用 WPA / WPA 2 的用户进行攻击,使受害者无法连接上 AP。这种方法即 RSN IE Poisoning。
Continue reading IEEE 802.11 Denial-of-Service: RSN IE Poisoning
One simple means to defend Wi-Fi availability
前面写了 3 篇有关如何攻击 Wi-Fi 可用性的 post,于是这里也来简单的介绍一下自己所想的一个非常简单的、用于保护 Wi-Fi 可用性的思路。现实生活中的情况总是复杂的,不过个人认为下面这个思路在理论上来看是成立的(也或许实践中早有公司应用),没有过多的问题,当然这也有它自身的局限性,似乎还没有一个足够完美的方案(如果有的话,业界应该早就推广开了)。
我们已经提到过三种攻击,分别是 Deauthentication Flood,Beacon Flood 和 Authentication Flood,这三种攻击都需要攻击者发送数量非常多的包才行。于是我们也可以反过来利用这一点。
Continue reading One simple means to defend Wi-Fi availability
IEEE 802.11 Denial-of-Service: Authentication Flood
这是另一个 IEEE 802.11 攻击的方法,算上前面两篇
- IEEE 802.11 Denial-of-Service: Deauthentication Attack
- IEEE 802.11 Attack: Beacon Flood
- IEEE 802.11 Denial-of-Service: Authentication Flood
就收集齐了 IEEE 802.11 中最简单的三种可用性攻击。这三种方法不涉及任何密码学的东西,仅仅需要靠近受害者的网络范围,然后嗅探到几个包就可以开始攻击,并且足以让被攻击的人完全用不了无线网络。
这篇 post 中所描述的 Authentication Flood 与第一个 Deauthentication Flood 相对应。Deauthentication Flood 是强制让一个 AP 上、已经建立 association 的 STA 断开,从而达到目的。而Authentication Flood 则是通过伪造一大堆请求认证的包(其实还有 Association Flood,与这篇 post 中的方法相似),来塞满 AP 中的 Authentication / Association table,这样,真正的用户只能等到这个表有空 entry 的时候才能和 AP 建立连接了。
Continue reading IEEE 802.11 Denial-of-Service: Authentication Flood
IEEE 802.11 Attack: Beacon Flood
这是另一种 802.11 攻击,或者说扰乱更合适。攻击者发出无数个 Beacon 帧,这些 Beacon 帧既可以是和你的 AP 拥有相同的 SSID,也可以是攻击者自定的 SSID,或者就是一些随机字符串,取决于攻击的目的和实际环境。
IEEE 802.11 Denial-of-Service: Deauthentication Attack
使用 WPA / WPA2 能让你的数据有更好的安全保障,但是攻击者可以利用基于802.11设计上的缺陷来对你进行拒绝服务攻击,也就是 deauthentication 攻击。攻击者首先需要知道你的 Wi-Fi 的 MAC 地址,然后伪装成你的身份给 AP (或者说路由器) 发送 deauthencation 包。这样一来,AP 在收到了来自“你”的 deauthencation 包之后,就会断开和你的连接。虽然仅仅是用这种方法并不能窃取到你的数据(结合其他方法有可能能破解 AP 的密码,但是不在本文的讨论范围之内),并且这个方法的目的也不是要窃听数据,而是让你连不上自家的 AP。如此一来,你也不得不拿出网线。而且不管你使用什么加密方式、密码强度有多高,甚至隐藏你的 SSID (毕竟隐藏 SSID 正如字面意义上的,它只是藏了 SSID,并不是隐藏了你和 AP 之间的数据包)都不行。
在 802.11 - 2012 标准 8.2.4.1.3 Type and Subtype fields 下面,列举了所有有效的 MAC 帧的 type 与 subtype 的组合,这里我们关注的 deauthentication 是 type 为 management 的帧。
Type valueb3 b2 | Typedescription | Subtype valueb7 b6 b5 b4 | Subtype description |
---|---|---|---|
00 | Management | ... | ... |
00 | Management | 1100 | Deauthentication |
00 | Management | ... | ... |
Continue reading IEEE 802.11 Denial-of-Service: Deauthentication Attack