Leetcode演算法【114. 二叉樹展開為鏈表】
- 2019 年 12 月 25 日
- 筆記
上周通過一位小夥伴，加入了一個氛圍很好的小群，人不多，但是大家保持著對知識的渴望，讓我很感動。
我自己也有一個群，人數也不多，但是能真正互動起來一起學習，一起進步的，還是太少。所以，現在也在學習如何讓自己成為更好的群主，帶動群活躍，帶動一個社群活躍，帶動小夥伴們一起進步，是我的願景。當然，也不否認現在很多群友正在朝著積極向上的方向走著，我要做的，也是時刻保持對知識的渴望，做到「持續學習」。
誰讓咱是一名優秀的程式設計師呢。上周日也學習了一遍遞歸，還通過一個二叉樹的例子來簡單介紹了下。我之前解決二叉樹相關的問題，基本上用的都是遞歸，結果那天分享的朋友用了隊列，讓我眼前一亮，原來程式的世界真是奇妙。
所以，思想碰撞真的是一件很開心的事情。大家在持續的學習，持續的交流中，會打開一些思維定式，接納更多的方式，你們覺得呢？
Algorithm LeetCode演算法
114. 二叉樹展開為鏈表 (https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)
題目描述：給定一個二叉樹，原地將它展開為鏈表。
例如，給定二叉樹
示例1：
1 / 2 5 / 3 4 6
將其展開為：
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/
解法：後序遍曆法
題目其實就是將二叉樹通過右指針，組成一個鏈表。
從例子上可以看出，其實就是讓我們把二叉樹，通過先序遍歷展示出來。所以我們首先想到的是能不能用先序遍歷的方式，每遍歷一個節點，就將上一個節點的右指針更新為當前節點。
先序遍歷的順序是 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原本的右節點就丟失了，也就是我們後續找不到5這個節點。
所以，又引起了我們的思考，如何才能不讓5丟失呢？後序遍歷可以嗎？
也就是我們依次遍歷6 5 4 3 2 1，然後每遍歷一個節點就將當前節點的右指針更新為上一個節點，如下：
遍歷到5，把5的右指針指向6，即變成6 <- 5 4 3 2 1
遍歷到4，把4的右指針指向5，即變成6 <- 5 <- 4 3 2 1
以此類推，因為我們更新當前右指針的時候，當前節點的右節點已經訪問過了，所以就不會存在丟失節點的問題。
把這個轉變成後序遍歷，遍歷順序就是 右子樹 -> 左子樹 -> 根節點
// 將二叉樹構建完成 public static void main(String[] args) { TreeNode treeNode = new TreeNode(1); treeNode.left = new TreeNode(2); treeNode.left.left = new TreeNode(3); treeNode.left.right = new TreeNode(4); treeNode.right = new TreeNode(5); treeNode.right.right = new TreeNode(6); flattern(treeNode); }
/** * * @Title : * @Description: 後續遍歷 * @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) { // 添加根節點 treeNodes.push(current); // 添加右節點 current = current.right; } // 已經訪問到最右邊的節點 current = treeNodes.peek(); // 當右節點已經被訪問過或者左節點不存在的情況，就去訪問根節點 if (current.left == null || current.left == preview) { treeNodes.pop(); current.right = preview; current.left = null; preview = current; current = null; } else { current = current.left; } } }
補充說明：先序遍歷
在介紹著後序遍歷的時候，我們先用先序遍歷的例子以及缺陷，來說明為什麼我們選擇後序遍歷。那麼，就一定不能用現需遍歷了嗎？顯然，答案是不對的。
有一種特殊的先序遍歷，提前將右節點保存到棧中，我們利用這種遍歷方式就可以防止右節點的丟失。因為棧是先進後出，所以我們先將右節點入棧。
再根據上面先序遍歷的分析，因為我們用棧保存了右孩子，所以不需要擔心右孩子丟失了。用一個 pre 變數保存上次遍歷的節點即可。
public static void flatten1(TreeNode root) { if (root == null){ return; } Stack<TreeNode> s = new Stack<TreeNode>(); s.push(root); TreeNode pre = null; while (!s.isEmpty()) { TreeNode temp = s.pop(); if(pre!=null){ pre.right = temp; pre.left = null; } if (temp.right != null){ s.push(temp.right); } if (temp.left != null){ s.push(temp.left); } pre = temp; } }
結語
二叉樹，是一顆神奇的樹，理論上我們都可以通過先序、中序、後續遍歷來拆解他，得到我們想要的結果，在做題的時候也是如此。
但是真正體現到編程的世界裡，還是和理論做題有一點不同，編程需要我們用機器語言是實現，去思考，去打通我們演算法的任督二脈，這樣就是LeetCode存在的魅力，他是一個氛圍很好的社區，擁有它，就擁有了演算法的世界，擁有了進階的可能。
安利了LeetCode，安利下自己的號，盡量做到每周一題，分模組的學習。小編最大的後悔就是沒能在大學學好數據結構和演算法這門課，現在吃虧了，吃大虧了。好在萬變不離其宗，只要通過自己的勤奮，沒有什麼是不可能的。
加油，奔跑吧兄弟們！
