大屄,日本三级网站豆花视频,亚洲黄色视,影音先锋在线亚洲av,亚洲丁香视先锋,97超碰站,日本高清视频在线,日韩黄色在线电影

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?將二叉搜索樹轉(zhuǎn)化為排序的雙向鏈表，我們先來看題面：

https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let's take the following BST as an example, it may help you understand the problem better:

將一個(gè)二叉搜索樹就地轉(zhuǎn)化為一個(gè)已排序的雙向循環(huán)鏈表?？梢詫⒆笥液⒆又羔樧鳛殡p向循環(huán)鏈表的前驅(qū)和后繼指針。

為了讓您更好地理解問題，以下面的二叉搜索樹為例：

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

我們希望將這個(gè)二叉搜索樹轉(zhuǎn)化為雙向循環(huán)鏈表。鏈表中的每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)和后繼指針。對(duì)于雙向循環(huán)鏈表，第一個(gè)節(jié)點(diǎn)的前驅(qū)是最后一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的后繼是第一個(gè)節(jié)點(diǎn)。

下圖展示了上面的二叉搜索樹轉(zhuǎn)化成的鏈表?！癶ead” 表示指向鏈表中有最小元素的節(jié)點(diǎn)。

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

特別地，我們希望可以就地完成轉(zhuǎn)換操作。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點(diǎn)的左指針需要指向前驅(qū)，樹中節(jié)點(diǎn)的右指針需要指向后繼。還需要返回鏈表中的第一個(gè)節(jié)點(diǎn)的指針。

下圖顯示了轉(zhuǎn)化后的二叉搜索樹，實(shí)線表示后繼關(guān)系，虛線表示前驅(qū)關(guān)系。

解題

解題思路：

這道題目實(shí)際上也是將二叉搜索樹序列化。

注意轉(zhuǎn)換規(guī)則：左指針指向前繼節(jié)點(diǎn)，右指針指向后繼節(jié)點(diǎn)。

實(shí)際上就是中序遍歷。

使用棧來幫助我們進(jìn)行中序遍歷。

在出棧時(shí)改變它的左指針，指向，前繼節(jié)點(diǎn)prev；prev的右指針指向當(dāng)前出棧的節(jié)點(diǎn)。

需要注意的是：在最后需要連接頭指針和尾指針。

class?Solution?{
public:
????Node* treeToDoublyList(Node* root) {
????????if(!root) return?root;
????????Node* cur = root;
????????stack stk;
????????Node* head = NULL;
????????Node* prev = NULL;
????????while(cur || !stk.empty()){
????????????if(cur){
????????????????stk.push(cur);
????????????????cur = cur->left;
????????????}else{
????????????????cur = stk.top();
????????????????stk.pop();
????????????????if(!head) head = cur;
????????????????if(prev){
????????????????????prev->right = cur;
????????????????????cur->left = prev;
????????????????}
????????????????prev = cur;
????????????????cur = cur->right;
????????????}
????????}
????????head->left = prev;
????????prev->right = head;
????????return?head;
????}
};

好了，今天的文章就到這里，如果覺得有所收獲，請(qǐng)順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。

上期推文：

LeetCode1-420題匯總，希望對(duì)你有點(diǎn)幫助！

LeetCode刷題實(shí)戰(zhàn)421：數(shù)組中兩個(gè)數(shù)的最大異或值

LeetCode刷題實(shí)戰(zhàn)422：有效的單詞方塊

LeetCode刷題實(shí)戰(zhàn)423：從英文中重建數(shù)字

LeetCode刷題實(shí)戰(zhàn)424：替換后的最長重復(fù)字符

LeetCode刷題實(shí)戰(zhàn)425：單詞方塊

?LeetCode刷題實(shí)戰(zhàn)426：將二叉搜索樹轉(zhuǎn)化為排序的雙向鏈表

解題