開啟演算法之門~01.翻轉演算法

前言

演算法,其實就是一個問題的解決方法，學習演算法的前提需要一定的《資料結構》基礎,才能夠更加容易學好演算法，本人呢是一名后端開發的程式猿,演算法學的其實并不算太好，所以才想著經常來練習提高自己的演算法水平,因此以后我也會經常把自己練習的筆記、經驗和總結給大家分享出來，當然了,如果有高手看到不足之處在評論區指點自然是更好不過的了，本專欄的博客呢,我也差不多是一周更新一兩次左右吧，因為平時也忙,我必須先把作業上的事情全部處理好才敢把時間放在其他地方，

抽象思維

我相信,對于學過資料結構的人來說一定是非常懂得如何去抽象一個問題的，因為學資料結構與演算法,如果不把問題抽象化去想的話,即使是把這個演算法寫了出來其實也僅僅只是把代碼背下來了而已,過不了多久還是會忘記的，演算法和編程語言沒有太大關系,如果說我用C語言可以實作的演算法,換成了Python,在知道Python語言語法的情況下卻無法實作的話,那只能證明自己只是把這個演算法給背下來了,但并沒有真正學會它，

之所以今天我叫他翻轉演算法,是因為我今天想實作一下鏈表的翻轉和二叉樹的翻轉,但一時也不知道叫什么所以就稱呼為翻轉演算法，由于這兩個演算法以前都寫過,所以今天就主要是強調思維程序,然后再來解題，

今天的主題

鏈表的翻轉(堆疊和佇列)

鏈表的翻轉(回圈遍歷)

二叉樹的翻轉(遞回法)

二叉樹的翻轉(回圈法(堆疊))

翻轉單鏈表

鏈表我們都知道,它是線性資料結構，所以說，要翻轉一個線性資料結構,只需要把順序變成逆序即可，我們還知道堆疊是先進后出,而佇列則是先進先出，鏈表的插入也有兩種,一種是順序插入,一種是逆序插入，順序插入的單鏈表就是每個新的元素都插入到尾部,所以一切都是按照順序的，比如我插入1,2,3,4,5,6,7,8,9，那么順序插入的單鏈表依然是1~9,而逆序插入就是每次都從頭部插入,所以逆序插入的單鏈表先進去的反而越來越靠后，因此逆序插入的單鏈表就是9,8,7,6,5,4,3,2,1，所以說,如果面對的單鏈表是采用順序插入則可以使用堆疊，因為堆疊是先進后出,直接把資料丟掉堆疊里面再吐出來重新存入即可，那么對于逆序插入的單鏈表則使用佇列，因為佇列是先進先出,逆序插入的單鏈表本來順序就已經是反的,再用堆疊反著來就相當于是還原,所以這種情況下使用先進先出的佇列反而可以成功，

其實對于一個問題的解決方法,并不是固定的,可以依據情況而來，可能有人會說,即使我是逆序的單鏈表,丟到堆疊里后再吐出來順序存進去不是也能達到效果嗎，這樣子說也沒毛病，這也更加證明了,演算法這種東西一定是要靠學會它,而不是背會它，因為背會了它,不一定能在適當的情況使用適當的演算法，

過去寫過相關的博客

單鏈表的操作

順序堆疊和鏈表堆疊

順序佇列和鏈表佇列

堆疊和佇列的翻轉方法

翻轉線性表,最省事的方法就是使用堆疊,特殊情況使用佇列，所以與其說這是在練習翻轉演算法倒不如說是在練習堆疊或者佇列，

當堆疊剛剛接收到鏈表資料的時候,如果只是遍歷堆疊自身的話,資料肯定和鏈表是相反的，但是如果重復存到鏈表里,已經反的資料再反一次就相當于還原了，這也是先進先出的佇列面對這種情況下為什么可以成功的原理，

/*
	佇列
	注意,該操作并非翻轉操作，堆疊才是翻轉操作，
	該操作的原因是因為鏈表本來就是反著插，所以順著來就可以了
*/
void reverseQueue() {
	Node* temp = head->next;
	//定義一個佇列
	int queue[MAXSIZE];
	int rear = -1,front = -1, i = 0, max = 0;
	//資料存到佇列里面
	while (temp) {
		queue[++rear] = temp->data;
		temp = temp->next;
	}
	//保存最大值
	max = rear;
	//重新初始化
	init();
	//再把佇列吐出來重新還給陣列
	for (i = 0; i <= max; i++) {
		addFirst(queue[++front]);
	}
}
/*
	堆疊
*/
void reverseStack() {
	Node* temp = head->next;
	//定義一個堆疊
	int stack[MAXSIZE];
	int top = -1,i = 0, max = 0;
	//資料存到堆疊里面
	while (temp) {
		stack[++top] = temp->data;
		temp = temp->next;
	}
	//保存最大值
	max = top;
	//重新初始化
	init();
	//再把堆疊吐出來重新還給陣列
	for (i = 0; i <= max; i++) {
		addFirst(stack[top--]);
	}
}

當我們插入鏈表結點的順序是逆序的時候,使用堆疊其實就是在把已經翻轉的資料又重新反轉了一遍,所以就變成還原，而佇列是把已經翻轉好的資料直接吐出來，所以這種情況下我們就使用佇列，

雖然說這種情況下不用佇列也可以，因為佇列本身并沒有起到翻轉的作用,只是因為該鏈表本身就是逆著插的，所以直接建立一個該鏈表的副本,把原鏈表置空再把副本的資料重新逆著插也能實作，

//這種寫法僅適用于逆著來的情況
Node *temp = head->next;
list = NULL;
while(temp){
	addFirst(temp->data);
	temp = temp->next
}

回圈翻轉

剛剛呢是使用堆疊或者佇列資料結構來輔助翻轉,那么還有很多其他的方法也可以實作反轉，就比如說我還知道一種通過鏈表輔助鏈表回圈的方式反轉,當然這么做就沒有堆疊或者佇列那么省事了，

void reverse() {
	// 定義一個輔助的指標, 遍歷原來的鏈表
	Node *cur = head->next;
	// 指向當前節點[cur]的下一個節點
	Node *next = (Node*) malloc(sizeof(Node));
	Node *reverseHead = (Node*) malloc(sizeof(Node));

	// 遍歷原來的鏈表，每遍歷一個節點，就將其取出，并放在新的鏈表 reverseHead  的最前端
	while (cur) {
		// 暫時保存當前節點的下一個節點
		next = cur->next;
		// 將 cur 的下一個節點指向新的鏈表的最前端
		cur->next = reverseHead->next;
		// 將 cur 連接到新的鏈表上
		reverseHead->next = cur;
		// 將 cur 后移
		cur = next;
	}
	// 將 head.next 指向 reverseHead.next, 實作單鏈表的反轉
	head->next = reverseHead->next;
	//釋放記憶體
	free(reverseHead);
	free(cur);
	free(next);
}

之所以結果是9 ~ 0是因為前面已經用佇列翻轉過一次了，，，所以最后一次的結果是以上一次結果的鏈表為準，0 ~ 9 翻轉完之后自然就是 9 ~ 0，就像我前面說的一樣，這種情況之所以堆疊不行是因為已經翻轉過的資料再翻轉一次肯定就是還原~

翻轉二叉樹

在翻轉二叉樹之前,有必要先考慮一下怎樣才算翻轉二叉樹，從圖片中就會發現,左邊的樹和右邊的樹它們的左右子樹全是反的，所以說,如果要翻轉二叉樹,只需要把左右子樹交換就可以了，我們可以使用遞回,因為遞回很省事，但是實際應用中是不建議使用遞回的,因為使用遞回一旦資料量大了就會出現堆疊溢位的情況,所以回圈還是比較靠譜的，

相關博客

樹與二叉樹

堆疊輔助遍歷二叉樹

遞回翻轉法

理論上說是不建議使用遞回,但是要學習演算法,所以這里也還是來實作一遍，其實使用遞回是一個比較省事的寫法,因為遞回可以直接從最下面的子節點開始進行左右子樹交換，注意要記得加個判斷,以免出現堆疊溢位的情況，

void recur_reverse(Tree *tree) {
	if (!tree) {
		return;
	}
	//先判斷是不是空
	if (tree->left != NULL) {
		//翻轉左子樹
		recur_reverse(tree->left);
	}
	if (tree->right != NULL) {
		//翻轉右子樹
		recur_reverse(tree->right);
	}
	//左右交換
	Tree* p = tree;
	if (p) {
		Tree* temp = p->left;
		p->left = p->right;
		p->right = temp;
	}
}

回圈翻轉法

除了遞回,這里還有一種方法就是回圈，因為遞回相比回圈而言不太適用于比較大的資料量，遞回不僅容易堆疊溢位,而且速度也比回圈慢，不過呢,學習的時候先使用遞回還是有好處的，因為遞回演算法的代碼層次分明,讀代碼的時候容易看得懂,也更容易知道演算法的原理，所以先用遞回實作一遍再去使用回圈可能在解題思維上會簡單很多，

在過去呢,我曾用堆疊輔助回圈遍歷過二叉樹，那么今天自然也可以使用堆疊來翻轉二叉樹，

void cycle_reverse(Tree *tree) {
	if (!tree) {
		return;
	}
	Tree* node = tree;
	//定義一個堆疊
	Tree* stack[MAXSIZE];
	int top = -1;
	//將tree放到堆疊的頭元素
	stack[++top] = tree;
	//回圈,堆疊為空結束
	while (top > -1) {
		//出堆疊
		tree = stack[top--];
		if (tree) {
			//左右子樹交換
			Tree* temp = tree->left;
			tree->left = tree->right;
			tree->right = temp;
			//左子樹不為空則左子樹入堆疊
			if (tree->left) {
				stack[++top] = tree->left;
			}
			//右子樹不為空則右子樹入堆疊
			if (tree->right) {
				stack[++top] = tree->right;
			}
		}
	}
}