二叉树后序遍历非递归实现

二叉树的遍历有递归实现的方式，前中后序遍历都非常直观易懂，缺点是递归始终是个开销可观的操作。非递归实现二叉树遍历不太易懂，尤其是后序遍历，这里把它记录下来以后回顾用。

二叉树后序遍历概念：对任一节点，它的左孩子总是先于它的右孩子被遍历到，它的右孩子总是先于该节点被遍历到。即是：左右中的顺序进行遍历。

算法和原理

感觉上看代码注释就能很好理解，树这种结构文字很难表述清楚。待我找到一个好的工具来画图，再看看能不能表达清楚～-～。建议读者自己在纸上模拟一次过程就能理解精髓了。主要是对二叉查找树的性质要够熟悉，其次对栈有基本的理解（先入后出）。

上代码

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
#include<iostream>
#include<stack>
#include"Header.h"
using namespace std;
// 二叉树插入的操作
void insert(Node<int>* root, int value) {
	if (root->val == value) {	// 拒绝重复的值
	}
	else if (root->val > value) {	// value在root左子树
		if (root->left == NULL) {	// root没有左子树，直接加一个节点
			root->left = new Node<int>();
			root->left->val = value;
			root->left->right = root->left->left = NULL;
			return;
		}
		insert(root->left, value);
	}
	else if (root->val < value) {   // value在root右子树
		if (root->right == NULL) {	// root没有右子树，直接加一个节点
			root->right = new Node<int>();
			root->right->val = value;
			root->right->right = root->right->left = NULL;
			return;
		}
		insert(root->right, value);
	}
}
int main() {
	Node<int>* root;			// 根节点
	Node<int>* tem;
	Node<int>* pre = NULL;      // pre 用来保存上一次弹出的节点的地址
	stack<Node<int>*> sta;		// 使用栈先入后出的特性来模拟遍历
	int n;
	int value;
	while (cin >> n) {
		cin >> value;
		root = new Node<int>();
		root->val = value;
		root->right = root->left = NULL;
		for (int i = 1; i < n; i++) {			// 输入一串数字，按逐个插入的原则，建二叉查找树，自己在纸上模拟下建个树更好理解
			cin >> value;
			insert(root, value);
		}
		while (!sta.empty()) sta.pop();		// 清空栈
		sta.push(root);
		pre = root;			// 这里将pre初始化为root，防止pre被更新前，任一节点的左右孩子之一是空导致判断复杂化。自己体会下
		while (!sta.empty()) {
			tem = sta.top();
			if (tem->left == pre || tem->right == pre || (!tem->left && !tem->right)) {	// 如果一个节点没有左右子节点，那么它作为根直接输出
				sta.pop();																// 如果它的左或右节点已经出过栈，说明它的左右子树都遍历过了，那么它也可以出栈了
				cout << tem->val << " ";												//  |
				pre = tem;																//  ↓
			}																			// 否则将它的左右节点入栈，刚好压在它头上。
			else {																		// 这就保证了如果一个节点root的左/右节点弹出（说明左右子树都遍历过了），那么当栈顶是root时，pre存的必然是它们之一。
				if (tem->right) {			// 先压入右节点，当然根节点是在右节点之前被压入过了。
					sta.push(tem->right);
				}
				if (tem->left) {			// 再压入左节点
					sta.push(tem->left);
				}							// 那就保证在出栈时，是按照左右中的顺序
			}
		}
	}
	return 0;
}

复杂度分析

时间复杂度：
O(n) 每个节点入栈一次出栈一次2n，没有额外的循环，常数去掉

空间复杂度：平均O(logn) 最坏O(n) 取决于二叉树的高度，如果是平衡二叉树那么就是O(logn)

全排列非递归实现

上次写了全排列的递归实现，简单分析了下时间和空间复杂度。元素个数比较多的时候递归实现的开销导致它几乎没有实用性了吧。学习过一些前辈总结的非递归实现后，觉得有必要把它记录下来。这里尽量讲清楚些，也算是对自己文字表达能力的训练吧。

全排列概念：

给定n个元素，输出所有不同的排列情况。

非递归原理

找到全排列中字典序最小的一个排列，然后找到字典序只比当前排列大的下一个排列，依次查找下去，一直到没有新的排列大于当前排列。

非递归实现算法

这里用一个int数组作为例子辅助说明。
[4, 6, 7, 2, 3, 1, 9]

  1. 对数组进行升序排序。 得到全排列中字典序最小的一个排列：[1, 2, 3, 4 ,6, 7, 9]
  2. 从后往前遍历，找到从最后一个元素往前最大的升序子串。假设该子串为 [k, n - 1]，那么也可以理解为k到n-1是递减的。
    • 如果k == 0，就例子而言，是这样的：[9, 7, 6, 4, 3, 2, 1]。那么其实我们已经找到字典序最大的一个排列，可以结束查找了。
    • 如果k > 0，比方说[1, 2, 3, 4, 9, 7, 6]，k = 5（值是9）。显然还有字典序更大的排列，转3
  3. 将[k, n - 1]区间中大于arr[k - 1]的数中最小的一个与 k - 1 位置的数对换，比方说[1, 2, 3, 4, 9, 7, 6] 变成了 [1, 2, 3, 6, 9, 7, 4]，这里6是区间中满足条件的数。再将区间[k, n -1]做升序排列，变成[1, 2, 3, 6, 4, 7, 9]。
    这里[1, 2, 3, 4, 9, 7, 6] 的下一个排列就是[1, 2, 3, 6, 4, 7, 9]。
  4. 重复2，3直到k == 0。

对算法的简单推理和证明

由于我们是从字典序最小的排列开始，一直到字典序最大的排列结束。那么我们只要证明：上面这个算法，它对一个排列，每次总是能得到字典序只比当前排列大的一个新的排列。就可以证明它的完备性了。
依然用[1, 2, 3, 4, 9, 7, 6] 辅助讲解。
对于这样的一个区间，我们把它划分成3个大区间。
A = [1, 2, 3]， arr[0]~arr[k - 2]
B = [4]， arr[k - 1]
C = [9, 7, 6]， arr[k]~arr[n -1]
C 代表从最后一个元素往前数最大的升序子串[k, n - 1]，B 是区间[k, n - 1]左边那个数–>arr[k - 1]， A 是 [0, k - 2]。A，B，C串起来是完整的一个排列。

再令到 D = B + C = [4, 9, 7, 6]，区间[k - 1, n - 1]。注意A和D串起来跟A，B, C串起来是同一个排列。

那么我们通过算法中的步骤2，找到D这个区间。
现在我们先来证明为什么只需要调整D区间，不需要调整A区间就能获得一个比原排列大的排列。
D区间中，第一个数是arr[k - 1]，我们总能在C区间中找到至少一个数arr[k+i]，比arr[k - 1]要大。那么把arr[k+i]与arr[k - 1]对调的话，就能在D区间上得到一个更大的排列。
为什么不能调整到A区间的元素呢？因为我们希望得到更大的字典序，所以只能对A调整使得A这一部分的字典序大于它原来的排列。但这种方式得到的排列，字典序必然大于只调整D区间的元素，这里读者自己简单推理下就明白了。
就例子而言：我们希望得到的排列是这样的 ：[1, 2, 3, ?, ?, ?, ? ] ，？号备选的数是：4, 6, 7, 9

然后来证明为何将C区间中的比arr[k - 1]大的数中的最小的一个与arr[k - 1]对调。
下面请时刻注意arr[k - 1]是D区间的开头，并且通常说到“排列”二字，是A区间不变，对D区间进行调整的排列。
D区间的元素可以分为3种类型，顺便说明下哪种类型能放到arr[k - 1]这个位置

  1. 小于arr[k - 1]的元素，这部分元素中的任一个调整到D区间的开头，得到的排列（D区间）都是比arr[k - 1]开头的排列要小的。不用考虑了。
  2. 等于arr[k - 1]的元素，注意我们是怎么找到C区间的，就可以知道D区间当前的排列其实是以arr[k - 1]开头的排列中最大的一个，不存在A不变，D区间以arr[k - 1]开头的更大的排列。
  3. 大于arr[k - 1]的元素，如果是希望找到最接近原排列的下一个排列，当然是找这其中最小的一个元素放到arr[k - 1]上啦。就例子来说，这个数是[6]，
    就例子而言：我们希望得到的排列是这样的：[1, 2, 3, 6, ?, ?, ?]，？号备选的数是：4, 7 , 9

现在我们已经把范围缩小到一定程度了。（其实你往前回顾可以看到我一直在缩小可能的区间，使得候选的排列越来越少，并且他们总是最接近原排列的）。
很显然只要把备选的部分[4, 7, 9]作升序排列并到尾部，就可以得到以[1, 2, 3, 6]开头的最小的排列了。
最后结果就是[1, 2, 3, 6, 4, 7, 9]。是字典序大于[1, 2, 3, 4, 9, 7, 6]的排列中最小的一个。

证毕。

上代码

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print_arr(vector<int>& arr, int n) {
	int i;
	for (i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
int main() {
	int n;
	int i, k;
	int tem;
	vector<int> arr;
	while (cin >> n) {
		arr.resize(n);
		for (i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr.begin(), arr.end());
		print_arr(arr, n);
		while (true) {
			for (k = n - 2; k >= 0; k--) {
				if (arr[k] < arr[k + 1]) {
					break;
				}
			}
			if (k < 0) {
				break;
			}
			// k > 0
			k += 1;  //   左开右闭区间 --> (k, n - 1]递减，改为左闭右闭区间 -->[k, n - 1]递减
			// 找到[k, n - 1]区间中大于 arr[k - 1]的数中，最小的一个
			for (i = n - 1; i >= k; i--) {
				if (arr[i] > arr[k - 1]) {
					break;
				}
			}
			swap(arr[k - 1], arr[i]);		// 交换
			// 逆序 [k, n - 1]，使得它递增
			for (i = k; i <= (k + (n - 1 - k) / 2); i++) {
				swap(arr[i], arr[n - 1 + k - i]);
			};
			print_arr(arr, n);
		}
	}
	return 0;
}

对比和分析

注意到非递归求全排列，是不会出现重复的排列的。

非递归实现全排列：
空间复杂度：O(n!)
时间复杂度：O(？) < O(n!n) 说实话这种情况我不会求，先给个范围，做个记号，后面回来修改。
为什么小于 O(n!n)呢？找到最长递减序列，最坏的情况也不过是最后一个数到第一个 –> O(n)，逆序也是O(n)。何况并不总是这样，因此不会超过O(n!n)。

递归实现全排列：
空间复杂度：O(n!)
时间复杂度：O(n!nlogn) 去重的情况

非递归没有函数栈，这个优势是很巨大的，同时理论时间复杂度更小。是一种更好的求全排列的方法。

终。

全排列递归实现

全排列的概念：

给定n个元素，输出所有不同的排列情况。

递归的思路：

例子：对于字符串 abcd的全排列，我们可以这样看待。
它的全排列应当是以字符串abcd中任一字符+其它字符的全排列：
就abcd这个例子，分以下情况：
a + bcd的全排列
b + acd的全排列
c + abd的全排列
d + abc的全排列

可以看到我们已经能构造出子问题了。
实现的方式就是分别将当前字符串每个位置分别与首字符作对换，然后求除首字符位置外的部分的全排列。一直这样递归下去。

上代码：

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
#include<iostream>
#include<vector>
using namespace std;
static vector<vector<char>> vec;
void swap(vector<char>& arr, int a, int b) {
	char tem = arr[a];
	arr[a] = arr[b];
	arr[b] = tem;
}
// n是原始的字符串长度，k - n区间的字符是需要进行全排列的部分。
void getPermutation(vector<char>& arr, int k, int n) {
	int i, size;
	if (k == n) {
		size = vec.size();
		vec.resize(vec.size() + 1);
		size = vec.size();
		vec[size-1].resize(n);
		for (i = 0; i < n; i++) {
			vec[size - 1][i] = arr[i];
		}
		return;
	}
	for (i = k; i < n; i++) {
		swap(arr, k, i);	// 将需要进行全排列的区段中的每一字符分别与该区段的首字符交换
		getPermutation(arr, k + 1, n);
		swap(arr, k, i);	// 恢复原状
	}
}
int main() {
	int n;
	while (cin >> n) {
		vector<char> arr(n, 0);
		for (int i = 0; i < n; i++) cin >> arr[i];
		getPermutation(arr, 0, n);	//  最初是对 0 - n这一区段进行全排列
		int count = vec.size();
		int size;
		for (int i = 0; i < count; i++) {
			size = vec[i].size();
			for (int k = 0; k < size; k++) {
				cout << vec[i][k];
			}
			cout << endl;
		}
	}
	return 0;
}

复杂度分析

时间复杂度：
O(n!)
空间复杂度：
O(n!)
函数栈的最大深度应该是 n，（除main函数）。但不幸的是实际上申请销毁函数栈的次数是n!，非常可怕的开销。所以这是一个效率低下的方法。
另一方面，使用vector来保存所有的排列情况，对于有重复元素的情况是不能做到去重的，其实可以考虑用set。set的数据结构是二叉查找树，每次插入是logn的复杂度，总的时间复杂度是O(n!logn)。我选择原地爆炸。

学习完字典序方式求全排列后会将更高效的方法写上来。有条件我会做效率对比。

以上。

KMP算法

KMP算法看过也用过很多次了。每次重新拿起来都要查博客+自己推导一次，这次决定写上博客吧。刚好这个新blog部署好没多久。
阮一峰前辈的博客总能给我很好的启发。把一个复杂或者难懂的问题讲清楚也是一种能力吧。
这里贴上参考的博客：字符串匹配的KMP算法 – 阮一峰

KMP算法的应用场景：

判断一个字符串A是否包含字符串B。

京东笔试编程题：烽火台,动态规划解法

题目：

战争游戏的至关重要环节就要到来了，这次的结果将决定王国的生死存亡，小B负责首都的防卫工作。首都处于一个四面环山的盆地中，周围的n个小山构成一个环，作为预警措施，小B计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。
一旦发生外敌入侵事件，山顶上的岗哨将点燃烽烟。若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，则岗哨可以观察到另一个山峰上的烽烟是否点燃。由于小山处于环上，任意两个小山之间存在两个不同的连接通路。满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。
小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，她希望你能够帮她解决这个问题。
输入
输入中有多组测试数据。每组测试数据的第一行为一个整数n（3 <=n <= 10^6），为首都周围的小山数量，第二行为n个整数，依次表示小山的高度h，（1 <= h <= 10^9）。
输出
对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。

样例输入

1
2
5
1 2 4 5 3

样例输出

1
7

分析

使用动态规划方法。
用两个二维数组分别记录，两座山峰顺时针方向和逆时针方向，中间山峰的最大高度。
然后遍历一次山峰对，求出满足条件的对数。既是两座山峰间山峰的最大高度同时小于等于它们，这里是一个环，因此要考虑顺时针和逆时针方向有一个满足条件就可以。

时间复杂度：O（n^2^)

代码:

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
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    while (cin >> n) {
        int heights[n];
        vector< vector<int> > dpClock(n , vector<int>(n , 0));   // 顺时针方向，两座山峰间的最大高度
        vector< vector<int> > dpReClock(n , vector<int>(n , 0));   // 逆时针方向，两座山峰间的最大高度
        int res = 0;
        for (int i = 0; i < n; i++) {	// 自己和自己中间是没有的，是0
            cin >> heights[i];
            dpClock[i][i] = 0;
            dpReClock[i][i] = 0;
        }
        for (int i = 0; i < n; i++) {	// 相邻两座山峰中间也是没有山峰的，最大高度是0
            dpClock[i][(i+1)%n] = 0;
            dpReClock[i][(i-1+n)%n] = 0;
        }
        for (int k = 2; k < n; k++) {	// 长度为k+1的山峰链，从3开始
            for (int i = 0; i < n; i++) {	// 山峰链 ： 顺时针：[i,i+k] 逆时针：[i-k, i]
                // （i,i+k）间的最高山峰高度，分两种情况
                // 1. 如果（i,i+k-1）间的最高山峰低于新增加的第i+k-1座山峰，那么更新最大高度为新增加的i+k-1座山峰的高度
                // 2. 否则，依然是(i,i+k-1)间的最大高度
                // 因为是环，所以要做特殊处理，越界时直接mod。
                dpClock[i][(i+k)%n] = heights[(i+k-1)%n] > dpClock[i][(i+k-1)%n] ? heights[(i+k-1)%n] : dpClock[i][(i+k-1)%n];
                // 逆时针方向同理
                dpReClock[i][(i-k+n)%n] = heights[(i-k+1+n)%n] > dpReClock[i][(i-k+1)%n] ? heights[(i-k+1+n)%n] : dpReClock[i][(i-k+1)%n];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
            // 排除自己看见自己的情况。
            // 如果两座山峰间，无论逆时针还是顺时针，中间所有山峰的高度都不大于它们两中任意一个，那么计数+1。
                if (i != k && 
                    (dpClock[i][k] <= heights[i] && dpClock[i][k] <= heights[k]
                || dpReClock[i][k] <= heights[i] && dpReClock[i][k] <= heights[k]))
                    res++;
            }
        }
        // 这里注意求的是对数
        cout << res/2 << endl;
    }
    return 0;
}