題目描述：

輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。

代碼實(shí)現(xiàn)：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
//解題思路：
//1.將左子樹(shù)構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點(diǎn)。
//2.定位至左子樹(shù)雙鏈表最后一個(gè)節(jié)點(diǎn)。
//3.如果左子樹(shù)鏈表不為空的話，將當(dāng)前root追加到左子樹(shù)鏈表。
//4.將右子樹(shù)構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點(diǎn)。
//5.如果右子樹(shù)鏈表不為空的話，將該鏈表追加到root節(jié)點(diǎn)之后。
//6.根據(jù)左子樹(shù)鏈表是否為空確定返回的節(jié)點(diǎn)。
public class Solution {
    // 記錄子樹(shù)鏈表的最后一個(gè)節(jié)點(diǎn)，終結(jié)點(diǎn)只可能為只含左子樹(shù)的非葉節(jié)點(diǎn)與葉節(jié)點(diǎn)
    TreeNode leftLast = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
    //public TreeNode Convert(TreeNode root) {
        if(pRootOfTree == null)
            return null;
        if(pRootOfTree.left == null&&pRootOfTree.right == null){
            leftLast = pRootOfTree;// 最后的一個(gè)節(jié)點(diǎn)可能為最右側(cè)的葉節(jié)點(diǎn)
            return pRootOfTree;
        }
        // 1.將左子樹(shù)構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點(diǎn)
        TreeNode left = Convert(pRootOfTree.left);
        // 3.如果左子樹(shù)鏈表不為空的話，將當(dāng)前root追加到左子樹(shù)鏈表
        if(left!=null){
            leftLast.right = pRootOfTree;
            pRootOfTree.left = leftLast;
        }
        leftLast = pRootOfTree;// 當(dāng)根節(jié)點(diǎn)只含左子樹(shù)時(shí)，則該根節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)
        // 4.將右子樹(shù)構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點(diǎn)
        TreeNode right = Convert(pRootOfTree.right);
        // 5.如果右子樹(shù)鏈表不為空的話，將該鏈表追加到root節(jié)點(diǎn)之后
        if(right!=null){
            right.left = pRootOfTree; 
            pRootOfTree.right = right;
        }
        if (left != null) {
            return left;
        }
        return pRootOfTree;
    }
}