資料結構與算法:二叉搜尋樹與雙向連結清單

描述

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

public class ConvertTree {

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

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

    TreeNode pre2 = null;
    TreeNode root2 = null;
    public TreeNode Convert2(TreeNode pRootOfTree){
        if(pRootOfTree == null){
            return null;
        }

        Convert2(pRootOfTree.left);

        if(null == root2){
            root2 = pRootOfTree;
        }

        if(null != pre2){
            pre2.right = pRootOfTree;
            pRootOfTree.left = pre2;
        }

        // 移動到下一個節點
        pre2 = pRootOfTree;
        Convert2(pRootOfTree.right);
        return root2;
    }

    /*
       二叉搜尋樹，左邊一直遞歸
       要有一個前驅pre節點。 遞歸到上一級的時候 root 就是pre的後繼。
       最終若傳回pre，那麼是降序排列，題幹要求升序，故儲存第一個節點，傳回第一個節點。
     */
    TreeNode pre= null;
    TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree ==null) {
            return null;
        }

        Convert(pRootOfTree.left);

        if(root == null){
            root=pRootOfTree;
        }

        if(pre!=null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }

        pre=pRootOfTree; // pre指向下一個節點
        Convert(pRootOfTree.right);
        return root;
    }

    public static void main(String[] args) {

        //System.out.println("main...");
    }
}