36-二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

如下是一棵二叉搜索树。

二叉搜索树

需要转换成双向链表。

双向链表

考虑到双向链表的性质，再看一下双向链表的顺序，刚好是二叉搜索树的中序遍历。

那么问题就转变为将二叉树中序遍历然后对每一个节点改变指向的问题。

第一种方法

我们可以先中序遍历，将节点顺次放到列表里，然后在遍历列表改变其指针指向。

private List<TreeNode> nodeList = new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        traverse(pRootOfTree); //顺次将节点放到nodeList中
        int length = nodeList.size();
        for (int i = 0; i < length - 1; i++) { //设置节点的右指针指向下一个节点
            TreeNode node = nodeList.get(i);
            TreeNode nextNode = nodeList.get(i + 1);
            node.right = nextNode;
        }
        for (int i = length - 1; i > 0; i++) {//设置节点的左指针指向前一个节点
            TreeNode node = nodeList.get(i);
            TreeNode preNode = nodeList.get(i - 1);
            node.left = preNode;
        }
        return nodeList.get(0);
    }
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        nodeList.add(root);
        traverse(root.right);
    }

这里要注意下，剑指offer里提到的是双向链表，而leetcode题目描述是双向循环链表，循环的意思是第一个节点的左指针要指向最后一个节点，最后一个节点的右指针要指向第一个节点。

第二种方法

还有一种递归方法，使用中序递归方法遍历二叉树，对每一个节点修改左右子树的指向。

递归三大件：终止方法、不重叠的缩小问题规模、结果的整合。

前两个都很简单，结果整合时需要注意使用一个尾结点指针，来连接后面的结点。

 private static class Node { //节点结构
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };

    private Node pre = null;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        traverse(root);
        while (root.left != null) {
            root = root.left;
        }
        pre.right = root;//设置第一个节点和最后一个节点的关联
        root.left = pre;
        return root;
    }

    public void traverse(Node node) {
        if (node == null) {
            return;
        }
        traverse(node.left);
        //以下几行代码实际还是要在中序遍历过程中处理，根本还是中序遍历
        node.left = pre; 
        if(pre != null){
            pre.right = node;
        }
        pre = node;
        traverse(node.right);
    }

这里得到的是双向循环链表。