面试题36：二叉搜索树和双向链表

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。假设左子树处理完了，就要处理根结点，而根结点必须知道左子树的最大结点，所以要用函数返回值记录下来；之后处理右子树，右子树的最小结点（也用中序遍历得到）要和根结点链接。
思路：使用中序遍历（左中右），默认按照从小到大排列，
解决方案：

public class Question36 {
    static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }
    public static BinaryTreeNode convert(BinaryTreeNode rootTree){
        if (rootTree == null) return null;
        BinaryTreeNode lastNodeInList = null;
        lastNodeInList = convertNode(rootTree, lastNodeInList);
        // 指向双向链表的尾节点，我们需要返回头节点
        BinaryTreeNode headOfList = lastNodeInList;
        while (headOfList != null && headOfList.left != null){
            headOfList = headOfList.left;
        }
        return headOfList;

    }
    private static BinaryTreeNode convertNode(BinaryTreeNode node, BinaryTreeNode lastNodeInList){
        // 处理左子树，获得最大节点
        BinaryTreeNode current = node;
        if(current.left != null){
            lastNodeInList = convertNode(current.left, lastNodeInList);
        }
        // 链接最大节点和根节点
        current.left = lastNodeInList;
        if (lastNodeInList != null){
            lastNodeInList.right = current;
        }
        // 处理右子树
        lastNodeInList = current;
        if (current.right != null){
            lastNodeInList = convertNode(current.right, lastNodeInList);
        }
        return lastNodeInList;
    }

    public static void main(String[] args) {
        BinaryTreeNode pHead = new BinaryTreeNode(1);
        BinaryTreeNode pAhead = new BinaryTreeNode(3);
        BinaryTreeNode pBhead = new BinaryTreeNode(5);
        BinaryTreeNode pChead = new BinaryTreeNode(7);
        BinaryTreeNode pDhead = new BinaryTreeNode(9);
        pHead.left = pAhead;
        pHead.right = pBhead;
        pBhead.left = pChead;
        pAhead.left = pDhead;

        System.out.println(convert(pHead).value);
    }
}