LCR 155. 將二叉搜索樹轉化為排序的雙向鏈表

LCR 155. 將二叉搜索樹轉化為排序的雙向鏈表

參考題解

前言

什么是循環雙鏈表？

雙向鏈表又稱雙鏈表，是鏈表的一種數據結構類型，其每個數據結點包含兩個指針，分別指向直接前驅和直接后繼，支持從前驅或后繼任意結點進行雙向遍歷。通常采用雙向循環鏈表結構實現，該結構通過頭尾結點互連形成閉環。

什么是二叉搜索樹？

關鍵性質：左 < 根 < 右

二叉搜索樹（BST）又稱二叉查找樹或二叉排序樹。

在二叉搜索樹中：

1. 若任意結點的左子樹不空，則左子樹上所有結點的值均不大于它的根結點的值。

2. 若任意結點的右子樹不空，則右子樹上所有結點的值均不小于它的根結點的值。

3. 任意結點的左、右子樹也分別為二叉搜索樹

中序遍歷

核心思想：左根右

解法思想

首先，從題目可以知道，最終要是要將二叉搜索樹轉換為一個已排序的雙向循環鏈表，而在二叉樹的遍歷中，中序遍歷恰好可以將一個二叉搜索樹轉換為一個有序地數組

因此，本題可以采用中序遍歷的思想

函數解析

dfs函數 – 深度優先遍歷

如果當前遍歷的節點為null，那就說明當前訪問的是葉子節點，直接返回。（因為深度優先遍歷函數遞下去完之后肯定是要從二叉樹的最下邊開始歸回來的）

遞歸當前的節點的左節點：dfs(cur.left)

構建雙鏈表：

• 判斷pre節點是否為null，如果是，那就說明當前節點cur是頭結點
• 如果不為null，那就 pre.right = cur，構建pre的后繼指針
• 接著構建cur的前驅指針，cur.left = pre
• 構建好當前節點之后，接著構建下一個節點，pre就要替代cur的位置
• 遞歸當前節點的右結點：dfs(cur.right)

public void dfs(Node cur) {
    if(cur == null) {
        return;
    }
    dfs(cur.left);
    if(pre != null) {
        pre.right = cur;
    } else {
        head = cur;
    } 
    cur.left = pre;
    pre = cur;
    dfs(cur.right);
}

treeToDoublyList函數

• 如果當前節點root為空，直接返回root或者null
• 轉化為雙鏈表：dfs(root)
• 構建循環雙鏈表：頭結點head要指向pre的后繼指針，pre指向head的前驅指針
• 返回head

關于pre：

在構建雙鏈表階段，當cur遍歷完最后一個節點的時候，就會繼續遍歷下一個節點，但下一個節點為null，而pre就會替代原本cur的位置，所以pre就會成為鏈表的尾結點。

public Node treeToDoublyList(Node root) {
    if(root == null) return root;
    dfs(root); // 構建雙鏈表
    head.left = pre;
    pre.right = head;
    return head; 
}

完整代碼展示

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return root;
        dfs(root); // 構建雙鏈表
        head.left = pre;
        pre.right = head;
        return head; 
    }

    public void dfs(Node cur) {
        if(cur == null) {
            return;
        }
        dfs(cur.left);
        if(pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        } 
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

end…