[[438991]]

Leetcode : https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_29_treeToDoublyList/Solution.java

二叉搜索樹轉換為雙向鏈表

“題目描述 ：輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的循環雙向鏈表。要求不能創建任何新的節點，只能調整樹中節點指針的指向。為了讓您更好地理解問題，以下面的二叉搜索樹為例：難度：中等

我們希望將這個二叉搜索樹轉化為雙向循環鏈表。鏈表中的每個節點都有一個前驅和后繼指針。對于雙向循環鏈表，第一個節點的前驅是最后一個節點，最后一個節點的后繼是第一個節點。下圖展示了上面的二叉搜索樹轉化成的鏈表。“head” 表示指向鏈表中有最小元素的節點。

特別地，我們希望可以就地完成轉換操作。當轉化完成以后，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向后繼。還需要返回鏈表中的第一個節點的指針。

解題思路：

本文解法基于性質：二叉搜索樹的中序遍歷為 遞增序列 。將 二叉搜索樹 轉換成一個 “排序的循環雙向鏈表” ，其中包含三個要素：

• 排序鏈表： 節點應從小到大排序，因此應使用 中序遍歷 “從小到大”訪問樹的節點。
• 雙向鏈表： 在構建相鄰節點的引用關系時，設前驅節點 pre和當前節點 cur，不僅應構建 pre.right = cur ，也應構建 cur.left = pre 。
• 循環鏈表： 設鏈表頭節點 head 和尾節點 tail ，則應構建 head.left = tail 和 tail.right = head 。

• 算法流程：dfs (cur)：遞歸法中序遍歷;
• 終止條件: 當節點cur為空，代表越過葉節點，直接返回;
• 遞歸左子樹，即 dfs(cur. left) ;
  • 構建鏈表:
  • 當 pre 為空時：代表正在訪問鏈表頭節點，記為head ;
  • 當 pre 不為空時：修改雙向節點引用，即pre.right = cur，cur. left = pre ;
• 保存cur：更新pre=cur,即節點cur后繼節點的pre;
• 遞歸右子樹，即dfs(cur. right) ; treeToDoublyList (root):
• 特例處理： 若節點root 為空,則直接返回;
• 初始化： 空節點pre ;
• 轉化為雙向鏈表： 調用dfs(root) ;
• 構建循環鏈表： 序遍歷完成后，head 指向頭節點，pre 指向尾節點，因此修改head 和pre的雙向節點引用即可;
• 返回值： 返回鏈表的頭節點head 即可;

復雜度分析:

• 時間復雜度0(N) ：N為二叉樹的節點數，中序遍歷需要訪問所有節點。
• 空間復雜度O(N) ：最差情況下，即樹退化為鏈表時，遞歸深度達到N，系統使用0(N)棧空間。

package com.nateshao.sword_offer.topic_29_treeToDoublyList; 
/** 
 * @date Created by 邵桐杰 on 2021/12/2 15:31 
 * @微信公眾號 程序員千羽 
 * @個人網站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 二叉搜索樹與雙向鏈表 
 */ 
public class Solution { 
 
    // 1. 中序，遞歸，來自解題大佬 
    Node pre, head; 
    public Node treeToDoublyList(Node root) { 
        // 邊界值 
        if(root == null) return null; 
        dfs(root); 
 
        // 題目要求頭尾連接 
        head.left = pre; 
        pre.right = head; 
        // 返回頭節點 
        return head; 
    } 
    void dfs(Node cur) { 
        // 遞歸結束條件 
        if(cur == null) return; 
        dfs(cur.left); 
        // 如果pre為空，就說明是第一個節點，頭結點，然后用head保存頭結點，用于之后的返回 
        if (pre == null) head = cur; 
            // 如果不為空，那就說明是中間的節點。并且pre保存的是上一個節點， 
            // 讓上一個節點的右指針指向當前節點 
        else if (pre != null) pre.right = cur; 
        // 再讓當前節點的左指針指向父節點，也就連成了雙向鏈表 
        cur.left = pre; 
        // 保存當前節點，用于下層遞歸創建 
        pre = cur; 
        dfs(cur.right); 
    } 
 
 
    /** 
     * 思路：定義一個鏈表的尾節點，遞歸處理左右子樹，最后返回鏈表的頭節點 
     * 
     * @param pRootOfTree 
     * @return 
     */ 
    public Node Convert(Node pRootOfTree) { 
        Node lastlist = coverNode(pRootOfTree, null); 
        Node pHead = lastlist; 
        while (pHead != null && pHead.left != null) pHead = pHead.left; 
        return pHead; 
 
    } 
 
    public Node coverNode(Node root, Node lastlist) { 
        if (root == null) return null; 
        Node cur = root; 
        if (cur.left != null) coverNode(cur.left, lastlist); 
        cur.left = lastlist; 
        if (lastlist != null) lastlist.right = cur; 
        lastlist = cur; 
        if (cur.right != null) lastlist = coverNode(cur.right, lastlist); 
        return lastlist; 
    } 
 
 
    class Node { 
        public int val; 
        public Node left; 
        public Node right; 
 
        public Node() { 
        } 
 
        public Node(int _val) { 
            val = _val; 
        } 
 
        public Node(int _val, Node _left, Node _right) { 
            val = _val; 
            left = _left; 
            right = _right; 
        } 
    } 
}