專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近在網(wǎng)上看到一個(gè)悲傷的故事，一網(wǎng)友把之前的兩段工作經(jīng)歷合并了，結(jié)果背調(diào)的時(shí)候沒通過，直接告訴他第二天不用入職了。我覺得應(yīng)該是公司不缺人，正好背調(diào)找個(gè)理由而已。招一個(gè)前端開發(fā)工程師最應(yīng)該看重的是技術(shù)能力，又不是招什么高管，還需要搞背調(diào)。
我記得在2017年找工作的時(shí)候也遇到過背調(diào)，那個(gè)背調(diào)公司不是很靠譜，背調(diào)結(jié)果中我的工作履歷斷的比較多，hrbp啥也沒說，后來我看到之后想要給他解釋，他說這些不用管，到時(shí)候直接來入職就行了。
之前背調(diào)都是委托第三方背調(diào)公司，他們通過查社保記錄可以確定在哪家公司工作過，不過也不是隨便查的，需要給你發(fā)個(gè)短信，經(jīng)過你的授權(quán)之后才能查，否則是查不了的，不知道現(xiàn)在這種背調(diào)公司還有沒有。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第114題：二叉樹展開為鏈表。
問題描述
來源：LeetCode第114題
難度：中等
給你二叉樹的根結(jié)點(diǎn) root ，請(qǐng)你將它展開為一個(gè)單鏈表：
1，展開后的單鏈表應(yīng)該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個(gè)結(jié)點(diǎn)，而左子指針始終為 null 。
2，展開后的單鏈表應(yīng)該與二叉樹先序遍歷順序相同。
示例1：
輸入：root = [1,2,5,3,4,null,6] 輸出：[1,null,2,null,3,null,4,null,5,null,6]
示例2：
輸入：root = [] 輸出：[]
樹中結(jié)點(diǎn)數(shù)在范圍 [0, 2000] 內(nèi)
-100 <= Node.val <= 100
問題分析
這題是讓把二叉樹展開為鏈表的形狀，實(shí)際上它不是一個(gè)鏈表，還是一棵二叉樹，只不過這棵二叉樹沒有左子樹只有右子樹，所以形狀像一個(gè)鏈表。
如果我們直接展開，也就是把二叉樹的左子樹放到右子樹上，那么右子樹上的節(jié)點(diǎn)就會(huì)被覆蓋，所以這種方式是行不通的。
這題要求的是展開之后的順序和二叉樹的前序遍歷順序相同，前序遍歷是：根節(jié)點(diǎn)->左子樹->右子樹。我們來逆向思考一下，如果對(duì)二叉樹的遍歷方式改成： 右子樹->左子樹->根節(jié)點(diǎn) ，這種方式相當(dāng)于鏈表的逆序遍歷，我們只需要在遍歷的時(shí)候把這些節(jié)點(diǎn)逆序串起來即可。
JAVA：
// 相當(dāng)于鏈表的頭節(jié)點(diǎn)，始終是變動(dòng)的。 TreeNode head = null; // 參照二叉樹的后序遍歷 public void flatten(TreeNode root) { if (root == null) return; flatten(root.right);// 先展開右子樹 flatten(root.left);// 在展開左子樹 // 操作當(dāng)前節(jié)點(diǎn) root.right = head; root.left = null;// 左子樹為空 head = root;// 更新head節(jié)點(diǎn) }C++：
public: // 相當(dāng)于鏈表的頭節(jié)點(diǎn)，始終是變動(dòng)的。 TreeNode *head = nullptr; void flatten(TreeNode *root) { if (root == nullptr) return; flatten(root->right);// 先展開右子樹 flatten(root->left);// 在展開左子樹 // 操作當(dāng)前節(jié)點(diǎn) root->right = head; root->left = nullptr;// 左子樹為空 head = root;// 更新head節(jié)點(diǎn) }筆者簡(jiǎn)介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼