JZ36 二叉搜索樹與雙向鏈表

描述

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表
註意:
1.要求不能創建任何新的結點，只能調整樹中結點指針的指向。當轉化完成以後，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向後繼
2.返回鏈表中的第一個節點的指針
3.函數返回的TreeNode，有左右指針，其實可以看成一個雙向鏈表的數據結構
4.你不用輸出雙向鏈表，程式會根據你的返回值自動列印輸出

思路：

二叉樹中序遍歷除了遞歸方法，我們還可以嘗試非遞歸解法，與常規的非遞歸中序遍歷幾乎相同，還是藉助棧來輔助，只是增加了連接節點。

具體做法：

step 1：創建兩個指針，一個指向題目中要求的鏈表頭（head），一個指向當前遍歷的前一節點（pre)，創建一個布爾型變數，標記是否是第一次到最左，因為第一次到最左就是鏈表頭。
step 2：判斷空樹不能連接。
step 3：初始化一個棧輔助中序遍歷。
step 4：依次將父節點加入棧中，直接進入二叉樹最左端。
step 5：第一次進入最左，初始化head與pre，然後進入它的根節點開始連接。
step 6：最後將右子樹加入棧中，棧中依次就彈出“左中右”的節點順序，直到棧為空。

代碼

package mid.JZ36二叉搜索樹與雙向鏈表;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
public class Solution {

    //頭節點
    private TreeNode head = null;

    //上一個節點
    private TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        //首先遞歸到最左最小值
        Convert(pRootOfTree.left);

        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pRootOfTree.left = pre;
            pre.right = pRootOfTree;
            pre = pRootOfTree;
        }
        //右遞歸
        Convert(pRootOfTree.right);
        return head;
    }
}