專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在網上看到一個悲傷的故事，一網友把之前的兩段工作經歷合并了，結果背調的時候沒通過，直接告訴他第二天不用入職了。我覺得應該是公司不缺人，正好背調找個理由而已。招一個前端開發工程師最應該看重的是技術能力，又不是招什么高管，還需要搞背調。

我記得在2017年找工作的時候也遇到過背調，那個背調公司不是很靠譜，背調結果中我的工作履歷斷的比較多，hrbp啥也沒說，后來我看到之后想要給他解釋，他說這些不用管，到時候直接來入職就行了。

之前背調都是委托第三方背調公司，他們通過查社保記錄可以確定在哪家公司工作過，不過也不是隨便查的，需要給你發個短信，經過你的授權之后才能查，否則是查不了的，不知道現在這種背調公司還有沒有。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第114題：二叉樹展開為鏈表。

問題描述

來源：LeetCode第114題

難度：中等

給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：

1，展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。

2，展開后的單鏈表應該與二叉樹先序遍歷順序相同。

示例1：

輸入：root = [1,2,5,3,4,null,6] 輸出：[1,null,2,null,3,null,4,null,5,null,6]

示例2：

輸入：root = [] 輸出：[]

• 樹中結點數在范圍 [0, 2000] 內

• -100 <= Node.val <= 100

問題分析

這題是讓把二叉樹展開為鏈表的形狀，實際上它不是一個鏈表，還是一棵二叉樹，只不過這棵二叉樹沒有左子樹只有右子樹，所以形狀像一個鏈表。

如果我們直接展開，也就是把二叉樹的左子樹放到右子樹上，那么右子樹上的節點就會被覆蓋，所以這種方式是行不通的。

這題要求的是展開之后的順序和二叉樹的前序遍歷順序相同，前序遍歷是：根節點->左子樹->右子樹。我們來逆向思考一下，如果對二叉樹的遍歷方式改成： 右子樹->左子樹->根節點 ，這種方式相當于鏈表的逆序遍歷，我們只需要在遍歷的時候把這些節點逆序串起來即可。

JAVA：

// 相當于鏈表的頭節點，始終是變動的。 TreeNode head = null; // 參照二叉樹的后序遍歷 public void flatten(TreeNode root) {     if (root == null)         return;     flatten(root.right);// 先展開右子樹     flatten(root.left);// 在展開左子樹     // 操作當前節點     root.right = head;     root.left = null;// 左子樹為空     head = root;// 更新head節點 }

C++：

public:     // 相當于鏈表的頭節點，始終是變動的。     TreeNode *head = nullptr;     void flatten(TreeNode *root) {         if (root == nullptr)             return;         flatten(root->right);// 先展開右子樹         flatten(root->left);// 在展開左子樹         // 操作當前節點         root->right = head;         root->left = nullptr;// 左子樹為空         head = root;// 更新head節點     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。