輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。
時間限制：1秒 空間限制：32768K

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

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

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        
    }
}

解題思路

1.簡單粗暴的辦法：先將二叉搜索樹進行中序遍歷并存入ArrayList中；
再對ArrayList中所有結(jié)點的left和right進行賦值即可，代碼如下：

import java.util.ArrayList;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        ArrayList<TreeNode> list=new ArrayList<TreeNode>();
        Sort(pRootOfTree,list);//對二叉搜索樹進行中序遍歷
        //對二叉搜索樹中所有結(jié)點的left和right進行賦值
        for(int i=0;i<list.size();i++){
            list.get(i).left=i==0?null:list.get(i-1);
            list.get(i).right=i==list.size()-1?null:list.get(i+1);
        }
        return list.get(0);
    }
    public void Sort(TreeNode pRootOfTree,ArrayList<TreeNode> list) {
        if(pRootOfTree.left!=null) Sort(pRootOfTree.left,list);
        list.add(pRootOfTree);
        if(pRootOfTree.right!=null) Sort(pRootOfTree.right,list);
    }
}