#yyds幹貨盤點# 面試必刷TOP101：二叉搜尋樹與雙向連結清單

1.簡述：

描述

輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。如下圖所示

資料範圍：輸入二叉樹的節點數 ，二叉樹中每個節點的值 要求：空間複雜度（即在原樹上操作），時間複雜度 

注意:

1.要求不能建立任何新的結點，隻能調整樹中結點指針的指向。當轉化完成以後，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向後繼2.傳回連結清單中的第一個節點的指針3.函數傳回的TreeNode，有左右指針，其實可以看成一個雙向連結清單的資料結構

4.你不用輸出雙向連結清單，程式會根據你的傳回值自動列印輸出

輸入描述：

二叉樹的根節點

傳回值描述：

雙向連結清單的其中一個頭節點。

示例1

輸入：

{10,6,14,4,8,12,16}      

傳回值：

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;      

說明：

輸入題面圖中二叉樹，輸出的時候将雙向連結清單的頭節點傳回即可。      

示例2

輸入：

{5,4,#,3,#,2,#,1}      

傳回值：

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;      

5
                  /
                4
              /
            3
          /
        2
      /
    1
樹的形狀如上圖      

public class Solution {
    //傳回的第一個指針，即為最小值，先定為null
    public TreeNode head = null;  
    //中序周遊目前值的上一位，初值為最小值，先定為null
    public TreeNode pre = null;   
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            //中序遞歸，葉子為空則傳回
            return null;     
        //首先遞歸到最左最小值  
        Convert(pRootOfTree.left); 
        //找到最小值，初始化head與pre
        if(pre == null){       
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //目前節點與上一節點建立連接配接，将pre設定為目前值
        else{       
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}