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

import java.util.*;
/**
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) {
        ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
        if (pRootOfTree != null) {
            if (pRootOfTree.left != null) {
                travel(pRootOfTree.left, arr);
            }
            arr.add(pRootOfTree);
            if (pRootOfTree.right != null) {
                travel(pRootOfTree.right, arr);
            }
        }else{
            return null;
        }
        if(arr.size() == 1){
            return pRootOfTree;
        }
        for(int i = 0; i < arr.size(); i++){
            if(i == 0){
                arr.get(0).right = arr.get(1);
                continue;
            }
            if(i == arr.size()-1){
                arr.get(arr.size()-1).left = arr.get(arr.size() -2);
                continue;
            }
            arr.get(i).left = arr.get(i-1);
            arr.get(i).right = arr.get(i+1);

        }
        return arr.get(0);
    }
    public void travel(TreeNode root, ArrayList<TreeNode> arr) {
        if (root != null) {
            if (root.left != null) {
                travel(root.left, arr);
            }
            arr.add(root);
            if (root.right != null) {
                travel(root.right, arr);
            }
        }
    }
}