/** *          4       /         2     5     / \         1   3     6   /  0    0<=>1<=>2<=>3<=>4<=>5<=>6   * */public class Solution {    public TreeNode BSTtoDLL(TreeNode root) {        TreeNode res = BSTtoList(root).head;        return res;    }    private NodePair BSTtoList(TreeNode root) {        if (root == null)            return null;        NodePair leftPair = BSTtoList(root.left);        NodePair rightPair = BSTtoList(root.right);        if (leftPair != null) {            leftPair.tail.right = root;            root.left = leftPair.tail;        }        if (rightPair != null) {            root.right = rightPair.head;            rightPair.head.left = root;        }        TreeNode newHead = root;        TreeNode newTail = root;        if (leftPair != null) {            newHead = leftPair.head;        }        if (rightPair != null) {            newTail = rightPair.tail;        }        return new NodePair(newHead, newTail);    }    private static class NodePair {        TreeNode head;        TreeNode tail;        public NodePair(TreeNode head, TreeNode tail) {            this.head = head;            this.tail = tail;        }    }    public static void main(String[] args) {        TreeNode root = new TreeNode(4);        root.left = new TreeNode(2);        root.right = new TreeNode(5);        root.left.left = new TreeNode(1);        root.left.right = new TreeNode(3);        root.left.left.left = new TreeNode(0);        root.right.right = new TreeNode(6);        System.out.println(new Solution().BSTtoDLL(root));    }}