本文解法基于性質：二叉搜索樹的中序遍歷為 遞增序列 ，
將 二叉搜索樹 轉換成一個 “排序的回圈雙向鏈表” ，其中包含三個要素：
1.排序鏈表： 節點應從小到大排序，因此應使用 中序遍歷
2.“從小到大”訪問樹的節點， 雙向鏈表： 在構建相鄰節點的參考關系時，設前驅節點 pre 和當前節點 cur ，
不僅應構建 pre.right= cur ，也應構建 cur.left = pre ，
3.回圈鏈表： 設鏈表頭節點 head 和尾節點 tail ，則應構建 head.left = tail 和 tail.right = head ，
雙指標：
class Solution {
private:
Node* head, * pre = NULL;
public:
Node* treeToDoublyList(Node* root) {//雙指標做法
if (!root) return NULL;
inorder(root);
head->left = pre;
pre->right = head;
return head;
}
void inorder(Node* root)
{
if (root == NULL)return;
inorder(root->left);
root->left = pre;
if (pre)
pre->right = root;
else head = root;
pre = root;
inorder(root->right);
}
};
陣列方法：很簡單就不做介紹了，就是先把節點都放進陣列然后在建立聯系，
Node* treeToDoublyList(Node* root) {
if (!root) return NULL;
vector<Node*> nodelist;
inorder(nodelist, root);
int l = nodelist.size();
if (l == 1)
{
nodelist[0]->right = nodelist[0];
nodelist[0]->left = nodelist[0];
return nodelist[0];
}
for (int i = 1; i < l - 1; i++) {
nodelist[i]->left = nodelist[i - 1];
nodelist[i]->right = nodelist[i + 1];
}
nodelist[0]->left = nodelist[l - 1];
nodelist[0]->right = nodelist[1];
nodelist[l - 1]->right = nodelist[0];
nodelist[l - 1]->left = nodelist[l - 2];
return nodelist[0];
}
void inorder(vector<Node*>& nodelist, Node* root)
{
if (root == NULL)return;
inorder(nodelist, root->left);
nodelist.push_back(root);
inorder(nodelist, root->right);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272588.html
標籤：其他