上周通過一位小伙伴，加入了一個氛圍很好的小群，人不多，但是大家保持著對知識的渴望，讓我很感動。
我自己也有一個群，人數(shù)也不多，但是能真正互動起來一起學習，一起進步的，還是太少。所以，現(xiàn)在也在學習如何讓自己成為更好的群主，帶動群活躍，帶動一個社群活躍，帶動小伙伴們一起進步，是我的愿景。當然，也不否認現(xiàn)在很多群友正在朝著積極向上的方向走著，我要做的，也是時刻保持對知識的渴望，做到“持續(xù)學習”。
誰讓咱是一名優(yōu)秀的程序員呢。上周日也學習了一遍遞歸，還通過一個二叉樹的例子來簡單介紹了下。我之前解決二叉樹相關的問題，基本上用的都是遞歸，結(jié)果那天分享的朋友用了隊列，讓我眼前一亮，原來程序的世界真是奇妙。
所以，思想碰撞真的是一件很開心的事情。大家在持續(xù)的學習，持續(xù)的交流中，會打開一些思維定式，接納更多的方式，你們覺得呢？
Algorithm LeetCode算法
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/(https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)
題目描述：給定一個二叉樹，原地將它展開為鏈表。
例如，給定二叉樹
示例1：
將其展開為：
1 \ 2 \ 3 \ 4 \ 5 \ 6
本文題解參考地址：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/
解法：后序遍歷法
題目其實就是將二叉樹通過右指針，組成一個鏈表。
從例子上可以看出，其實就是讓我們把二叉樹，通過先序遍歷展示出來。所以我們首先想到的是能不能用先序遍歷的方式，每遍歷一個節(jié)點，就將上一個節(jié)點的右指針更新為當前節(jié)點。
先序遍歷的順序是 1->2->3->4->5->6，如下：
遍歷到2，把1的右指針指向2，即變成 1->2 3 4 5 6
遍歷到3，把2的右指針指向3，即變成 1->2->3 4 5 6
理想狀況下，以此類推即可。
但是，如果我們把1的右指針指向2，那么這時候1原本的右節(jié)點就丟失了，也就是我們后續(xù)找不到5這個節(jié)點。
所以，又引起了我們的思考，如何才能不讓5丟失呢？后序遍歷可以嗎？
也就是我們依次遍歷6 5 4 3 2 1，然后每遍歷一個節(jié)點就將當前節(jié)點的右指針更新為上一個節(jié)點，如下：
遍歷到5，把5的右指針指向6，即變成6 <- 5 4 3 2 1
遍歷到4，把4的右指針指向5，即變成6 <- 5 <- 4 3 2 1
以此類推，因為我們更新當前右指針的時候，當前節(jié)點的右節(jié)點已經(jīng)訪問過了，所以就不會存在丟失節(jié)點的問題。
把這個轉(zhuǎn)變成后序遍歷，遍歷順序就是 右子樹 -> 左子樹 -> 根節(jié)點
/** * * @Title : * @Description: 后續(xù)遍歷 * @param treeNode * @return :void * @throws */public static void flattern(TreeNode root) { Stack<TreeNode> treeNodes = new Stack<>(); TreeNode current = root; TreeNode preview = null; while (current != null || !treeNodes.isEmpty()) { while (current != null) { // 添加根節(jié)點 treeNodes.push(current); // 添加右節(jié)點 current = current.right; } // 已經(jīng)訪問到最右邊的節(jié)點 current = treeNodes.peek(); // 當右節(jié)點已經(jīng)被訪問過或者左節(jié)點不存在的情況，就去訪問根節(jié)點 if (current.left == null || current.left == preview) { treeNodes.pop(); current.right = preview; current.left = null; preview = current; current = null; } else { current = current.left; } }}補充說明：先序遍歷
在介紹著后序遍歷的時候，我們先用先序遍歷的例子以及缺陷，來說明為什么我們選擇后序遍歷。那么，就一定不能用先序遍歷了嗎？顯然，答案是不對的。
有一種特殊的先序遍歷，提前將右節(jié)點保存到棧中，我們利用這種遍歷方式就可以防止右節(jié)點的丟失。因為棧是先進后出，所以我們先將右節(jié)點入棧。
再根據(jù)上面先序遍歷的分析，因為我們用棧保存了右孩子，所以不需要擔心右孩子丟失了。用一個 pre 變量保存上次遍歷的節(jié)點即可。
結(jié)語
二叉樹，是一顆神奇的樹，理論上我們都可以通過先序、中序、后續(xù)遍歷來拆解他，得到我們想要的結(jié)果，在做題的時候也是如此。
但是真正體現(xiàn)到編程的世界里，還是和理論做題有一點不同，編程需要我們用機器語言是實現(xiàn)，去思考，去打通我們算法的任督二脈，這樣就是LeetCode存在的魅力，他是一個氛圍很好的社區(qū)，擁有它，就擁有了算法的世界，擁有了進階的可能。
安利了LeetCode，安利下自己的號，盡量做到每周一題，分模塊的學習。小編最大的后悔就是沒能在大學學好數(shù)據(jù)結(jié)構(gòu)和算法這門課，現(xiàn)在吃虧了，吃大虧了。好在萬變不離其宗，只要通過自己的勤奮，沒有什么是不可能的。
作者：Dimple
