二叉搜索树与双向链表（java）

题目描述：

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

分析：

二叉搜索树转换为排序双向链表

由于要求转换后的链表有序，很自然的想到中序遍历二叉树。
当遍历到根节点的时候，我们把树分成三部分：值为10的结点，根节点为6的左子树、根节点为14的右子树。根据排序链表的定义，值为10的结点将和它的左子树的最大的一个结点（即值为8的结点）链接起来，同时它还将和右子树最小的结点（即值为12的结点）链接起来，如图：

把二叉搜索树分成三部分

显然，对于左右子树如何转换成一个排序的链表，其排序和转换的过程是一样的，自然要用到递归。

解答：

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

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

    }

}
*/
public class Solution {
    private TreeNode pre = null; //保存当前节点的前一个节点
    private TreeNode head = null;//保存链表的头结点
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        inOrder(pRootOfTree);
        return head;
    }
    private void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        node.left = pre;
        if (pre != null)  pre.right = node;
        pre = node;
        if (head == null) head = node;
        inOrder(node.right);
    }
    
}

运行结果

方法二：

如上是递归调用中序遍历的方法，下面给出不使用递归方法的解法,其实更加适合理解。在非递归方法中，我们用一个栈来保存找到树的最左节点时走过的了路径，然后依次出栈，修改出栈元素的left和right指针即可。

/*如下，是非递归的方法：用一个栈来保存遍历的顺序*/
    public static TreeNode ConvertWithStack(TreeNode pRootOfTree) {
        //如果根节点为null，则直接返回null
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode newHead = null;
        //否则，用cur记录当前节点，初始时指向根节点
        TreeNode cur = pRootOfTree;
        //prenode用来记录当前节点的前一个节点
        TreeNode prenode = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.isEmpty() || cur != null) {
            //左子树上的节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //到了树的最左边时，将栈中的节点出栈
            cur = stack.pop();
            //初始时，prenode为null,将最左边的节点赋值给newHead,也同时赋值给prenode
            if (prenode == null) {
                newHead = cur;
                prenode = cur;
            }
            //prenode有值的时候，让前一个指针的右节点指向当前节点，当前节点的左指针指向前一个节点
            else {
                prenode.right = cur;
                cur.left = prenode;
                prenode = cur;
            }
            //遍历当前节点的右孩子
            cur = cur.right;
        }
        return newHead;
    }