题解 | #二叉搜索树与双向链表#

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

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

    }

}
*/
//题目：不创建新的节点，将二叉搜索树转换为链表
//思路：中序遍历二叉搜索树，保存到列表中，然后对列表中节点的左右指针进行修改。
import java.util.*;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return pRootOfTree;
        ArrayList<TreeNode> list = new ArrayList<>();
        Convert(list,pRootOfTree);
        return Convert(list);
    }

    public void Convert(ArrayList<TreeNode> list, TreeNode node){
        if(node.left != null)
            Convert(list,node.left);
        list.add(node);
        if(node.right != null)
            Convert(list,node.right);
    }

    public TreeNode Convert(ArrayList<TreeNode> list){
        //注意此处数组越界：ArrayList.size()返回的是数组中元素个数，从0开始要减一
        for(int i=0;i<list.size()-1;i++){
            list.get(i+1).left = list.get(i);
            list.get(i).right = list.get(i+1);
        }
        return list.get(0);
    }
}